C++ Coding Exercise – Sort Colors (Bucket Sort and Dutch Flag)

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Submit your solution at: https://leetcode.com/problems/sort-colors/

STL:sort

I know, using stl:sort or you can just sort the array using one of your favorite sorting algorithms.

1
2
3
4
5
6

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

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

Bucket Sort

The values are ranged from 0 to 2, so we can count and put them in 3 buckets.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int c[3] = {0};
        for (int i = 0; i < nums.size(); i ++) {
            c[nums[i]] ++; // count
        }
        int j = 0;
        for (int i = 0; i < c[0]; i ++) {
            nums[j ++] = 0;
        }
        for (int i = 0; i < c[1]; i ++) {
            nums[j ++] = 1;
        }
        for (int i = 0; i < c[2]; i ++) {
            nums[j ++] = 2;
        }
    }
};

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int c[3] = {0};
        for (int i = 0; i < nums.size(); i ++) {
            c[nums[i]] ++; // count
        }
        int j = 0;
        for (int i = 0; i < c[0]; i ++) {
            nums[j ++] = 0;
        }
        for (int i = 0; i < c[1]; i ++) {
            nums[j ++] = 1;
        }
        for (int i = 0; i < c[2]; i ++) {
            nums[j ++] = 2;
        }
    }
};

This is the essence of the bucket sorting algorithm.

Dutch National Flag Problem (DNF)

This is the DNF [wiki] where we can use two pointers, the start and end, to point to the 0 and 2 respectively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int j = 0;
        for (int i = 0; i < n; i ++) {
            if (nums[i] == 0) {
                swap(nums[j ++], nums[i]);
            } else if (nums[i] == 2) {
                swap(nums[-- n], nums[i --]);
            }
        }
    }
};

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int j = 0;
        for (int i = 0; i < n; i ++) {
            if (nums[i] == 0) {
                swap(nums[j ++], nums[i]);
            } else if (nums[i] == 2) {
                swap(nums[-- n], nums[i --]);
            }
        }
    }
};

We go through each element one by one, if we find 0, we swap it to the red flag pointer and increment the pointer. If we find Blue flag, we swap it to the blue flag pointer and decrement it. Once it has been swapped, we need to decrease the array size by one so that the sorted blue flags won’t be visited again.

O(n) time, 1 pass, and O(1) space complexity.

–EOF (The Ultimate Computing & Technology Blog) —