Cacher is the code snippet organizer for pro developers

/**
 * 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++;
        }
    }
}