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]
We will use counting sort. Counting sort works for array of integers and will use a size k aux array, k is the number of different kinds of integer in the array. The aux array will store the frequency of the integers
Two pass algorithm
Use standard counting sort
void sortColors(vector<int>& nums) {
std::vector<int> freq(3, 0);
for(int i = 0; i < nums.size(); i ++){
freq[nums[i]] += 1;
}
int pos = 0;
for(int i = 0; i < freq.size(); i ++){
for(int j = pos; j < freq[i] + pos; j ++){
nums[j] = i;
}
pos += freq[i];
}
}
We first record the freq of each integer. Then we iterate through frequencies list and for each frequency about number x, we will fill the number list with x from [pos, pos + freq of x].
bugs
I was using a position to record the current position. But forgot to update it properly; I just assign pos = freq[i] instead of adding.When we use a position counter in a for loop, but not incremented by a for loop, that counter is usually accumulated through +=
one pass algorithm
Ideas
We have three colors, we the sorted array will have the form [0,0,0,0….1,1,1,1…2,2,2,2]. We will use 3 ptrs to partition the solutions
3 ptrs, 4 intervals
- Ptr0, left of this pts is 0. [begin, Ptr0) are all 0
- Ptr1, [Ptr0, Ptr1) are all 1
- Ptr2, (Ptr2, end] are all 2. also [Ptr1, Ptr2] are unknown
We have 4 intervals and the goal is to “squeeze out” the unknown and keep the other three in order.
[0,0,0,0,1,1,1,1,1,1,1, 2,2,2,2,2]
^ ^ ^
ptr0 ptr2 ptr1
We can see that [begin, ptr0) are all 0, [ptr0, ptr1) are all 1, (ptr2, end] are all 2. and unknown is empty because ptr2 < ptr1.
Base case for the loop invariant
In the beginning, we initiate Ptr0 = Ptr1 = 0. Ptr2 = end.
We have all 0 in [begin, 0) = empty, all 1 in [0, 0) = empty, all 2 in (end,end] = empty. Also the unknowns are in [ptr1, ptr2] = whole array.
Iteration step of the loop invariant
Goal of iteration and terminating condition
The goal is to squeeze out the unknown in [ptr1, ptr2]. So we use ptr1 as the iterating pointer and the termination condition is ptr1 > ptr2.
We should keep the 4 intervals consistent.
if nums[ptr1] == 0
We will swap nums[ptr0] with nums[ptr1] and increment both ptr0 and ptr1.
Before
[0,0,0....,0,1,1,1,1,1,1,0, ...]
^ ^
ptr0 ptr1
Before we swap, we know what’s on nums[ptr0] must be a 1 because [ptr0,ptr1) are all 1. So we need to
- put the 0 found in nums[ptr1] to nums[ptr0] and increment ptr0 so [begin, ptr0) are all 0.
- Put the 1 that was in nums[ptr0] in nums[ptr1] and increment ptr1 to maintain [ptr0, ptr1) are all 1
After
[0,0,0....,0,0,1,1,1,1,1,1,unknown ...]
^ ^
ptr0 ptr1
if nums[ptr1] == 1
We just increment ptr1 by 1 so [ptr0, ptr1) are all 1 and ptr1 points to another unknown
If nums[ptr1] == 2
before
[1,1,1,1,1,1 ,2,unkonwn,unkonwn...2,2,2,2,2]
^ ^
ptr1 ptr2
We want to put the 2 in nums[ptr2] and also don’t want to lose any entry, so we swap ptr1 with ptr2.
After the swap, ptr2 will point to 2 so we need to decrement (move ptr2 toward begin) ptr2.
But ptr1 still points to unknown so we don’t move ptr2.
AFter
[1,1,1,1,1,1 ,unknown,unkonwn,2...2,2,2,2,2]
^ ^
ptr1 ptr2
In the end, ptr1 will cross ptr2 and we have put all the unknown into the right place.
class Solution {
public:
void sortColors(vector<int>& nums) {
int ptr0 = 0; //left of ptr is all 0
int ptr1 = 0; //btw ptr0, ptr1 is 1
int ptr2 = nums.size() - 1; //right of ptr are all 2
//undefined(unsorted) nums are btween ptr1 and ptr2
while(ptr1 <= ptr2){// still have undefined numbers
if(nums[ptr1] == 0){
int temp = nums[ptr1];
nums[ptr1] = nums[ptr0];
nums[ptr0] = temp;
//after swap, increment both
ptr0 ++;
ptr1 ++;
}
else if(nums[ptr1] == 1){
ptr1 ++;
}
else{
int temp = nums[ptr1];
nums[ptr1] = nums[ptr2];
nums[ptr2] = temp;
ptr2 --;
}
}
}
};
Take away,
When you see the input is integral and we want to sort them, think counting sort.