Cacher is the code snippet organizer for pro developers

//  0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2
//          ^         ^
//          |         |
//       zero_end     |
//                    |
//                 two_begin
//      i should always be between [zero_end, two_begin]

void sort_colors(int A[], int N) {
    int zero_end = 0, two_begin = N-1;
    int i = 0;
    while(i <= two_begin) {                 // gist, cannot write i < N!!!
        if(A[i] == 1) {
            i++;
        }
        else if(A[i] == 0) {
            swap(A[zero_end++], A[i++]);
        }
        else if(A[i] == 2) {
            swap(A[two_begin--], A[i]);     // i stays
        }
    }
}

============== sort k colors ==================

http://blog.welkinlan.com/2015/08/25/sort-colors-i-ii-leetcode-lintcode-java/


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?


method 1: similar to above

class Solution {
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */
    public void sortColors2(int[] colors, int k) {
        int pl = 0;
        int pr = colors.length - 1;
        int i = 0;
        int min = 1, max = k;
        while (min < max) {
            while (i <= pr) {
                if (colors[i] == min) {
                    swap(colors, pl, i);
                    i++;
                    pl++;
                } else if (colors[i] == max) {
                    swap(colors, pr, i);
                    pr--;
                } else {
                    i++;
                }
            }
            i = pl;
            min++;
            max--;
        }
    }
    
    private void swap(int[] colors, int i, int j) {
        int temp = colors[i];
        colors[i] = colors[j];
        colors[j] = temp;
    }
}


method 2: counting sort
class Solution {
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */
    public void sortColors2(int[] colors, int k) {
        int[] bucket = new int[k];
        for (int color : colors) {
            bucket[color-1]++;
        }
        int index = 0;
        for (int i = 0; i < k; i++) {
            while (bucket[i]>0) {
                colors[index++] = i+1;
                bucket[i]--;
            }
        }
    }
}