Sorting as much as possible: values can travel no more than k positions to their left

Question

Given an array of length N and an integer K, sort the array as much as possible such that no element travels more than K positions to its left. An element however can travel as much as it likes to its right.

Let's define sortedness as the number of disordered pairs, i.e.: sortedness(1,2,3) = 0 and sortedness(3,1,2) = 2.

Clarification: If the first k+1 items of the array are moved to the end of the array, the other ones should be considered moved k+1 positions to the left.

This is an interview question. I thought of using a bubble sort. The outer loop would run K times with a run-time of O(nk). The smallest integer would be the only integer shifted to the left K times. The other integers would be shifted to the left less than K times.

Is there a more efficient way to approach this problem?

Answer 1

Use a min heap to sort the list of n elements in O(n log k).

1. Add the first k+1 unsorted elements to the heap.
2. Repeat this step: pop off the min element from the heap. Add it to the end of the sorted list. add the next unsorted element to the heap.

Because the heap always has at most k+1 elements regardless of n, all heap operations are O(log k), and the total running time is O(n log k)

Why is this correct?

Suppose it isn't. Then for some inputs my algorithm gives non-optimal sorts. Let I be such an input, let A be the output of my algorithm on I, and let B be the optimal sort.

Let i be the first index where A and B disagree. Let x = A[i], y = B[i], and let j be the index of x in B.

I claim that swapping x and y in B improve the sortedness of B, which is a contradiction.

Because A and B are identical for positions before i, the same set of k+1 elements are eligible to go into position i for both. Because my algorithm chose x to be the min of those elements, we know that x is less than y. We also know j is greater than i.

What happens when we swap x and y in B?

First, note that the change in sortedness is unaffected by anything to the left of i or to the right of j, because their positions relative to both x and y are unchanged by the swap.

We know there are no elements between i and j that are less than x, because my sort chose the smallest available element. Therefore all elements between i and j are at least as large as x.

For each element between i and j equal to x, swapping x and y improves sortedness by 1 because we improve y relative to these elements and x is unaffected.

For each element between i and j greater than x, the sortedness of x relative to these is improved by 1, and in the worst case the sortedness of y relative to these is degraded by 1, so the net effect is at worst 0.

Furthermore, swapping x and y improves the sortedness of x relative to y by 1, so this swap strictly improves overall sortedness.

Contradiction.