Produce a nearly sorted (or K sorted) array

Question

Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time. For example, let us consider k is 2, an element at index 7 in the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array. I'm looking for code review, best practices, optimizations etc. Also for some reason I could not get assertarrayequals hooked up so tested arrays unconventionally. Please ignore that as part of feedback

public final class KSortedArray {

    private KSortedArray() { } 

    /**
     * Returns the sorted array provided the input array is k-sorted.
     * If input array is not k-sorted, then results are unpredictable.
     * 
     * @param arr   The k-sorted array
     * @param k     the value of k, the deviation of placement.
     * @return      the sorted array
     */
    public static int[] kSortDontModifyInput(int[] arr, int k) {
        int[] n = new int[arr.length];

        final Queue<Integer> queue = new PriorityQueue<Integer>(k + 1);
        for (int  i = 0; i <= k; i++) {
            queue.add(arr[i]);
        }

        int ctr = 0;
        for (int i = k + 1; i < arr.length; i++) {
            n[ctr++] = queue.poll();
            queue.add(arr[i]);
        }
        while (!queue.isEmpty()) {
            n[ctr++] = queue.poll();
        }
        return n;
    }

    /**
     * Sorted array provided the input array is k-sorted.
     * If input array is not k-sorted, then results are unpredictable.
     * 
     * @param arr   The k-sorted array
     * @param k     the value of k, the deviation of placement.
     */
    public static void kSortMoidifyInput(int[] arr, int k) {
        Queue<Integer> queue = new PriorityQueue<Integer>(k + 1);
        for (int  i = 0; i <= k; i++) {
            queue.add(arr[i]);
        }
        int ctr = 0;
        for (int i = k + 1; i < arr.length; i++) {
            arr[ctr++] = queue.poll();
            queue.add(arr[i]);
        }

        while (!queue.isEmpty()) {
            arr[ctr++] = queue.poll();
        }
    }

    public static void main(String[] args) {
        int arr[] = {2, 6, 3, 12, 56, 8};

        int[] expected = {2, 3, 6, 8, 12, 56};
        int[] actual = kSortDontModifyInput(arr, 3);
        kSortMoidifyInput(arr, 3);
        for (int i = 0; i < expected.length; i++) {
            Assert.assertEquals(expected[i], actual[i]);
            Assert.assertEquals(expected[i], arr[i]);
        }
    }
}

Answer 1

When you use a class in a 'hacky' way, like you do by using a PriorityQueue as a TreeSet, you should make sure that you document why the class is used, and what properties of the class are being leveraged.

Your code does not work in O(n log(k) ) time because it uses a PriorityQueue, which has O( log(n) ) time-complexity for add():

Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size)

Your algorithm is not correct for the requirements given:

• For a start, it will fail for input where the input array is smaller than k. It will throw an ArrayIndexOutOfBoundsException.

• Secondly, you are working in k+1 space instead of k. Why? Where is the comment?

Further, because you auto-box all your values to Integer, from int, you have a significant performance penalty. If you keep your data as primitives (and use an array of primitives rather than a PriorityQueue), you will have better results.

The algorithm you need you use is strongly hinted at by the complexity requirement...

O( n log(k) ) strongly implies that you need to iterate over each value once, and, with that element, there is an O(log(k)) way to sort it.

For the loop, think a for-loop. For the log(k), think a binary search....

for (int i = 0; i < data.length; i++) {
    int from = i > k ? i - k : 0;
    int val = data[i];
    int pos = Arrays.binarySearch(data, from, i, val);
    if (pos < 0) {
        pos = -pos - 1;
    }
    System.arraycopy(data, pos, data, pos+1, i - pos - 1);
    data[pos] = val;
}

Answer 2

kSortDontModifyInput() and kSortMoidifyInput() use the same algorithm to do the sorting. The only difference is that kSortDontModifyInput() creates a new array instead of using the given one. Therefor you can implment kSortDontMoidifyInput() by making a copy of the input array and passing it to kSortMoidifyInput(). Since they are meant to be doing the same operation, if you find a bug in one, you don't have to remember to change the other one.