Star

LintCode: Rainbow Sort

Posted on | In |

Question

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.

k <= n

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

Explanation

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public void sortColors2(int[] colors, int k) {
    if (colors == null || colors.length == 0) {
        return;
    }
    rainbowSort(colors, 0, colors.length - 1, 1, k);
}
public void rainbowSort(int[] colors,
                        int left,
                        int right,
                        int colorFrom,
                        int colorTo) {
    if (colorFrom == colorTo) {
        return;
    }
    if (left >= right) {
        return;
    }
    int colorMid = (colorFrom + colorTo) / 2;
    int l = left, r = right;
    while (l <= r) {
        while (l <= r && colors[l] <= colorMid) {
            l++;
        }
        while (l <= r && colors[r] > colorMid) {
            r--;
        }
        if (l <= r) {
            int temp = colors[l];
            colors[l] = colors[r];
            colors[r] = temp;
            l++;
            r--;
        }
    }
    rainbowSort(colors, left, r, colorFrom, colorMid);
    rainbowSort(colors, l, right, colorMid + 1, colorTo);
}