Minimizing Number of inversions (prove a solution wrong)

Revision en3, by Agassaa, 2016-06-06 16:06:49

I came across a problem in stackoverflow. The problem gives you an array and a value 'K'. You can move an element to right at any position, but you can't move it more than K positions left. Find the optimal ordering on which number of inversions is minimum, e.g. array 3,2,1 has 3inversions. For K=1, solution array is: 2,1,3.

I had a greedy algorithm for this problem, but can't prove its correctness (though I'm pretty sure about its correctness):

iterate the array from left to right.
For each position i we consider a subarray from i to i+k. Then we find the minimum valued element on this subarray and insert this element at the beginning of the subarray and right shift the rest of elements.
Now, go to position i+1 and do the same.

for example:

given array = 5 3 4 7 8 2 1 0 and K = 2

this algorithm gets the solution array as this:

3 4 5 2 1 0 7 8
minimum inversion value = 12

this is just a naive version of algorithm which we can make faster as O(nlogn).

But is this correct at all? Help is greatly appreciated.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Agassaa 2016-06-06 21:13:18 2 Tiny change: 'K = 2`\n\nthis algori' -> 'K = 2`\n\nThis algori'
en6 English Agassaa 2016-06-06 18:00:04 7
en5 English Agassaa 2016-06-06 17:13:02 50
en4 English Agassaa 2016-06-06 16:10:01 28
en3 English Agassaa 2016-06-06 16:06:49 2 Tiny change: '2,1` has `2`inversion' -> '2,1` has `3`inversion'
en2 English Agassaa 2016-06-06 16:05:42 8
en1 English Agassaa 2016-06-06 16:01:32 1138 Initial revision (published)