leetcode-problems/75. Sort Colors.cpp at main · emonislive/leetcode-problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    void swap(vector<int>& nums, int firstIndex, int secondIndex) {
        int temp = nums[firstIndex];
        nums[firstIndex] = nums[secondIndex];
        nums[secondIndex] = temp;
    }

    int pivot(vector<int>& nums, int pivotIndex, int lastIndex) {
        int swapIndex = pivotIndex;
        for (int i = pivotIndex + 1; i <= lastIndex; i++) {
            if (nums[i] < nums[pivotIndex]) {
                swapIndex++;
                swap(nums, swapIndex, i);
            }
        }

        swap(nums, pivotIndex, swapIndex);
        return swapIndex;
    }

    void quickSort(vector<int>& nums, int firstIndex, int lastIndex) {
        if (firstIndex >= lastIndex)
            return;

        int pivotIndex = pivot(nums, firstIndex, lastIndex);
        quickSort(nums, firstIndex, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, lastIndex);
    }

    void sortColors(vector<int>& nums) {
        int firstIndex = 0;
        int lastIndex = nums.size() - 1;

        quickSort(nums, firstIndex, lastIndex);
    }
};