# LC75. Sort Colors

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

1. Ptr0, left of this pts is 0. [begin, Ptr0) are all 0
2. Ptr1, [Ptr0, Ptr1) are all 1
3. 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

1. put the 0 found in nums[ptr1] to nums[ptr0] and increment ptr0 so [begin, ptr0) are all 0.
2. 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.

Posted on Categories Leetcode