wayetan

12/30/2013 - 1:38 AM

Sort Colors

```
/**
* Given an array of n objects with k different colors (numbered from 1 to k),
* sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.
* Example:
* Given colors=[3, 2, 2, 1, 4], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4].
* Note:
* You are not suppose to use the library's sort function for this problem.
* Challenge:
* A rather straight forward solution is a two-pass algorithm using counting sort.
* That will cost O(k) extra memory. Can you do it without using extra memory?
*/
class Solution {
/**
* @param colors: A list of integer
* @param k: An integer
* @return: nothing
*/
/**
* Thoughts: Quick Sort, doing quick sort partition for K-1 times.
* 1. Use K-1 value as pivor
* 2. Starting from 0, whenever low < high && less or equal to pivot, low++
* 3. Starting from end, whenever high > 0 && greater than pivot, high--
* 4. Result: only swap when low and high have disagreement on the pivot value
*/
public void sortColors2(int[] colors, int k) {
// write your code here
int startIndex = 0, endIndex = colors.length - 1;
int startColor = 1, endColor = k;
while(startColor < endColor) {
int s = startIndex, p = startIndex, e = endIndex;
while(p <= e) {
if(colors[p] == startColor) {
swap(colors, p, s);
s++;
p++;
} else if(colors[p] == endColor) {
swap(colors, p, e);
e--;
} else
p++;
}
startIndex = s;
endIndex = e;
startColor++;
endColor--;
}
}
private void swap(int[] A, int index1, int index2) {
int tmp = A[index1];
A[index1] = A[index2];
A[index2] = tmp;
}
}
```

```
/**
* 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.
* Note:
* You are not suppose to use the library's sort function for this problem.
* 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 an one-pass algorithm using only constant space?
*/
public class Solution {
public void sortColors(int[] A) {
int red = -1;
int white = 0;
int blue = A.length;
while(white < blue){
if(A[white] == 0){
// it's red and swap red and white. And count red move forward by 1.
red++;
int temp = A[white];
A[white] = A[red];
A[red] = temp;
// white move forward as well.
white++;
}else if(A[white] == 2){
// it's blue and swap blue and white. And count blue move backward by 1.
blue--;
int temp = A[white];
A[white] = A[blue];
A[blue] = temp;
}else
white++;
}
}
public void sortColors(int[] nums) {
// write your code here
int p0 = -1, p1 = 0, p2 = nums.length;
while(p1 < p2) {
if(nums[p1] == 0) {
// swap 0 and 1
p0++;
int tmp = nums[p1];
nums[p1] = nums[p0];
nums[p0] = tmp;
p1++;
} else if(nums[p1] == 2) {
// swap 0 and 2
p2--;
int tmp = nums[p1];
nums[p1] = nums[p2];
nums[p2] = tmp;
} else
p1++;
}
}
}
```