Sort Color II

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.

Notice

You are not suppose to use the library's sort function for this problem.

Example

Given colors=[3, 2, 2, 1, 4],k=4, your code should sort colors in-place to[1, 2, 2, 3, 4].

Analysis: a quicksort algorithm can easily solve this problem. but how to make k useful? K can be used the pival reference.

public void sortColors2(int[] colors, int k) {
        int low = 0;
        int high = colors.length - 1;
        qsort(colors, low, high);        
    }

    public void qsort(int[] colors, int low, int high){
        if (low >= high){
            return;
        }        
        int pival = partition(colors, low, high);
        qsort(colors, low, pival - 1);
        qsort(colors, pival + 1, high);        
    }

    public int partition(int[] colors, int low, int high){
        if (colors.length <= 1){
            return colors[0];
        }

        int pos = high;
        int p = colors[high];        

        while (true){            
            while (colors[low] < p){
                low++;
                if (low > high){
                    break;
                }
            }            
            while (colors[high] >= p){
                high--;
                if (low > high){
                    break;
                }
            }
            if (low >= high){
                break;
            }
            swap(colors, low, high);            
        }        
        swap(colors, pos, low);        
        return low;
    }

    public void swap(int[] colors, int p1, int p2){
        int temp = colors[p1];
        colors[p1] = colors[p2];
        colors[p2] = temp;
    }