Problem description:

Given an array with n objects colored red, white or blue, sort them in-place 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.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
Could you come up with a one-pass algorithm using only constant space?

Solution:

We can use three pointers to solve this question.
low: point to 0
mid: point to 1
high: point to 2

If we encounter a 0, we know that it will be on the low end of the array, and if we encounter a 2, we know it will be on the high end of the array.

To achieve this in one pass without preprocessing (counting), we simply traverse the unknown will generating the low and high ends.

Take this example:

Assume our input is: 1 0 2 2 1 0 (short for simplicity).

Running the algorithm by hand would look something like:

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
38
39
40
41
42
43
44
45
46
47
48
1 0 2 2 1 0
^         ^
L         H
M

Mid != 0 || 2
Mid++

1 0 2 2 1 0
^ ^       ^
L M       H

Mid == 0
Swap Low and Mid
Mid++
Low++

0 1 2 2 1 0
  ^ ^     ^
  L M     H

Mid == 2
Swap High and Mid
High--

0 1 0 2 1 2
  ^ ^   ^
  L M   H

Mid == 0
Swap Low and Mid
Mid++
Low++

0 0 1 2 1 2
    ^ ^ ^
    L M H

Mid == 2
Swap High and Mid
High--

0 0 1 1 2 2
    ^ ^
    L M
      H

Mid <= High is our exit case
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low= 0, mid= 0, high= nums.size()-1;
        while(mid <= high){
            if(nums[mid] == 0){
                swap(nums[mid], nums[low]); //change the value in position 'mid', 'low'
                low++;
                mid++;
            }
            else if(nums[mid] == 1){ 
                mid++;
            }
            else{
                swap(nums[mid], nums[high]);
                high--;
            }
        }
    }
};

reference:
https://goo.gl/iKdeLx