Rainbow Sort III

(laicode Class99)

Given an array of balls with k different colors denoted by numbers 1- k, sort the balls.

Examples

• k=1, {1} is sorted to {1}
• k=3, {1, 3, 2, 1, 2} is sorted to {1, 1, 2, 2, 3}
• k=5, {3, 1, 5, 5, 1, 4, 2} is sorted to {1, 1, 2, 3, 4, 5, 5}

Assumptions

• The input array is not null.
• k is guaranteed to be >= 1.
• k << logn.

Analysis

link: https://piazza.com/class/j0eqhhdregb3i?cid=399

可以每次sort 两个 color, 把 sort k colors 问题转化成 k/2个 sort two colors 的问题。

假设 k 个 color 分别用1, 2, ..., k 个数来表示，每一次可以 sort其中的一对：<1, k>, <2, k-1>, ...

Time = O(nk/2) = O(nk)

Space = O(1)

Answer from forum

public int[] rainbow(int[] array, int k) {
    if (array == null || array.length < 2) {
        return array;
    }
    int left = 0;
    int right = array.length - 1;
    for (int round = 1; round <= k / 2; round++) {
        // since leftColor + rightColor == k + 1
        int leftColor = round;
        int rightColor = k + 1 - round;
        for (int i = left; i <= right; i++) {
            if (array[i] == leftColor) {
                swap(array, i, left);
                left++;
            } else if (array[i] == rightColor) {
                swap(array, i, right);
                i--;
                right--;
            }
        }
    }
    return array;
}

private void swap(int[] array, int left, int right) {
    int tmp = array[left];
    array[left] = array[right];
    array[right] = tmp;
}