Sort array in the minimum number of moves

Question

It is theoretically possible to sort an array in length(array) - length(longestIncreasingSubsequence(array)) moves by moving only elements that are not already in sorted order.

If the only operation allowed is an in place move, by removing an element from index A and reinserting it into index B, one element at a time, how would you generate the correct moves to end up with the sorted array? Again, there should be length(array) - length(longestIncreasingSubsequence(array)) moves required.

For example, here is an array:

[ 1, 8, 5, 2, 4, 6, 3, 9, 7, 10 ]

The longest increasing subsequence is:

[ 1, 2, 4, 6, 7, 10 ]

The indices of those elements are:

[ 0, 3, 4, 5, 8, 9 ]

So, the indices we need to move are:

[ 1, 2, 6, 7]

since those are the indices that are not already in sorted order.

In order to end up with a sorted array, the final indices of those 4 elements are:

[ 7, 4, 2, 8]

So, we need to simultaneously move index 1 to index 7, index 2 to index 4, index 6 to index 2, and index 7 to index 8. The problem is that when an element is moved, the other elements are shifted around making the later move operations invalid. I've tried transforming these indices, but so far have not come up with the correct list of moves required. Any ideas?

Hopefully I've explained the problem well enough. Please ask questions and I will clarify. Thanks!

Answer 1

Your problem is that the source positions are expressed in the prior order while the destination positions are in the final order. When you do 1->7, you don't know yet where 7 is in the prior order. You need to make adjustments for all the moves.

The original moves are:

from: [ 1, 2, 6, 7]
to:   [ 7, 4, 2, 8]

Step 1

Let's first tranform the positions as if we were removing all elements first, then inserting the elements at the new positions. For the from positions, proceed from the left: removing at 1 shifts positions (2,6,7) down to (1,5,6). Removing at 1 again shifts (5,6) down to (4,5). Removing at 5 shifts the 5 down to 4. For every position in from all subsequent positions with a larger or equal index must be decremented. We get:

from: [ 1, 1, 4, 4]

For the to positions, proceed from the end: Position 8 is correct. Position 2 is also correct, but it means the prior (7,4) were actually (6,3) at the time of insertion. So we adjust them. Similarily, inserting at 3 means the prior position 6 was at 5.

So, for the to array, we proceed from the end, for every position we decrement all prior positions that have a larger index. The to array becomes:

to:   [ 5, 3, 2, 8]

Step 2

What we have is the correct positions for 4 removals followed by 4 insertions. Now we want to interleave the removals and the insertions.

Insertion at 5 must be done before the removals at (1, 1, 4). 5 is larger than any of these, so it won't affect the positions (1, 1, 4), but the 5 is affected because the 3 removals are done left of the insertion point. 5 becomes 8.

Insertion at 3 must come before removals at (4, 4). Since 3 is smaller than the 4's, the position 3 is unaffected by the removals but the removals must be incremented, to positions (5, 5).

Insertion at 2 comes before the last removal at 5 (was 4). It is smaller, therefore the 5 is adjusted to 6.

General method for step 2:

for i = 0 to size-1
    for j = size-1 to i+1
        if from[j] < to[i] then increment to[i]
        else increment from[j]

We should get the arrays:

from: [ 1, 1, 5, 6]
to:   [ 8, 3, 2, 8]

These are the final moves to execute with the correct positions at the time of the move. The moves can be read from left to right: Remove at 1, insert at 8. Remove at 1, insert at 3. Remove at 5, insert at 2. Remove at 6, insert at 8.