Sort Colors @LeetCode

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.

click to show follow up.

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?

	package leetcode;
	/**
	* Solution: Three pointer-- O(n) one pass. Counting Sort -- O(n) two pass, Bubble Sort -- O(n^2)
	* At first, I use general two point, i and tail. But it doesn't work. Can't handle "1" easily.
	* redIndex and blueIndex is a smart way.
	*
	* Reference: http://fisherlei.blogspot.com/2013/01/leetcode-sort-colors.html
	* @author jeffwan
	* @date Apr 2, 2014
	*/
	public class SortColors {
	/*
	* Define two pointer, redPointer, bluePointer. O(n) Time, O(1) Space.
	* scan from i to blueIndex.(i could be equlas to blueIndex!)
	* 1. 0 -> move to redIndex. redIndex++, i++
	* 2. 1 -> i++
	* 3. 2 -> move to blueIndex. blueIndex--;
	* 4. We can't i++ after swap with blueIndex, because we don't know if new number is 0, 1 ,2. But we can i++ fater swap with
	* redIndex, because all redIndex points to 0(except for 1st time).
	*/
	public void sortColors(int[] A) {
	if (A == null || A.length == 0) {
	return;
	}
	int redIndex = 0;
	int blueIndex = A.length - 1;
	int i = 0;
	while (i <= blueIndex) {
	if (A[i] == 0) {
	swap(A, redIndex, i);
	i++;
	redIndex++;
	} else if (A[i] == 1) {
	i++;
	} else {
	swap(A, blueIndex, i);
	blueIndex--;
	}
	}
	}
	private static void swap(int[] A, int i, int j) {
	int temp = A[i];
	A[i] = A[j];
	A[j] = temp;
	}
	/*
	* Solution provided by problem. -- Counting Sort. O(n) --> two pass
	* 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.
	*/
	public void sortColors1(int[] A) {
	if (A == null || A.length == 0) {
	return;
	}
	int[] count = new int[3];
	for (int i = 0; i < A.length; i++) {
	if (A[i] == 0) {
	count[0]++;
	} else if (A[i] == 1) {
	count[1]++;
	} else {
	count[2]++;
	}
	}
	int i = 0;
	for (int k = 0; k < count.length; k++) {
	while (count[k] > 0) {
	A[i] = k;
	i++;
	count[k]--;
	}
	}
	}
	// Brute Force. Bubble Sort O(n^2)
	public void sortColors2(int[] A) {
	if (A == null || A.length == 0) {
	return;
	}
	for (int i = 0; i < A.length - 1; i++) {
	for (int j = i + 1; j < A.length; j++) {
	if (A[i] > A[j]) {
	int temp = A[j];
	A[j] = A[i];
	A[i] = temp;
	}
	}
	}
	}
	}

view raw SortColors.java hosted with ❤ by GitHub