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 `23`inversions. 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.<br>↵
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.<br>↵
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` <br> `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.↵
↵
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.<br>↵
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.<br>↵
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` <br> `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.↵
