75. Sort Colors

Build-in Function

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
    }
};

• T: $O(n \cdot \log n)$
• S: $O(1)$

Binary Search

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        quickSort(nums, 0, nums.size() - 1);
    }

    void quickSort(vector<int>& nums, int left, int right)
    {
        if (left < right)
        {
            int pivot = partition(nums, left, right);
            quickSort(nums, 0, pivot - 1);
            quickSort(nums, pivot + 1, right);
        }
    }

    int partition(vector<int>& nums, int left, int right)
    {
        int pivot = nums[right];
        int pointer = left;
        for (int i = left; i < right; ++i)
        {
            if (nums[i] <= pivot)
            {
                swap(nums[i], nums[pointer]);
                ++pointer;
            }
        }
        swap(nums[pointer], nums[right]);
        return pointer;
    }
};

• T: $O(n \cdot \log n)$

• S: $O(1)$

• Bubble Sort

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        int n = nums.size();
        bool swapped = false;
        for (int i = 0; i < n; ++i)
        {
            swapped = false;
            for (int j = 0; j < n - 1 - i; ++j)
            {
                if (nums[j] > nums[j + 1])
                {
                    swap(nums[j], nums[j + 1]);
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }
};

• T: $O(n^2)$

• S: $O(1)$

• Merge Sort

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        mergeSort(nums, 0, nums.size() - 1);
    }

    void merge(vector<int>& nums, int left, int mid, int right)
    {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        vector<int> l1(n1);
        vector<int> l2(n2);

        // 將 nums 數列左側的數字填入 l1
        for (int i = 0; i < n1; ++i) l1[i] = nums[left + i];
        // 將 nums 數列右側的數字填入 l2
        for (int i = 0; i < n2; ++i) l2[i] = nums[mid + 1 + i];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2)
        {
            if (l1[i] <= l2[j])
            {
                nums[k] = l1[i++];
            }
            else
            {
                nums[k] = l2[j++];
            }
            ++k;
        }
        while (i < n1)
        {
            nums[k] = l1[i];
            ++i; ++k;
        }
        while (j < n2)
        {
            nums[k] = l2[j];
            ++j; ++k;
        }
    }
    void mergeSort(vector<int>& nums, int left, int right)
    {
        if (left < right)
        {
            int mid = (left + right) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            merge(nums, left, mid, right);
        }
    }
};

• T: $O(n \cdot \log n)$
• S: $O(n)$