Rainbow Sort

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].

Solution:

Rainbow sort solves the same problem in Counting Sort.

1. Initial count = 0.

2. Find min and max of the array

3. Partition all min numbers to the left end of the array and all max numbers to the right end of the array

4. Repeat Step 1 and Step 2 for middle part and increase k by 2.

5. Stop until count >= k

Code:

public void sortColors2(int[] colors, int k) {
        if (colors == null || colors.length == 0) {
            return;
        }
        int count = 0;
        int start = 0;
        int end = colors.length - 1;
        while (count < k) {
            //find the min and max
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            for (int i = start; i <= end; i++) {
                min = Math.min(min, colors[i]);
                max = Math.max(max, colors[i]);
            }

            //partition them to left and right
            int left = start;
            int right = end;
            int cur = left;
            while (cur <= right) {
                if (colors[cur] == min) {
                    //since cur starts from left, 
                    //if both colors[cur] and colors[left] are same, they have to increase simultaneously
                    swap(colors, cur++, left++);
                } else if (colors[cur] == max) {
                    swap(colors, cur, right--);
                } else {
                    cur++;
                }
            }

            //repeat with count += 2 and left right as start and end respectively
            count += 2;
            start = left;
            end = right;
        }
    }
    private void swap(int[] colors, int a, int b) {
        int temp = colors[a];
        colors[a] = colors[b];
        colors[b] = temp;
    }