Sorting an array in a minimum number of moves

Question

Theoretically, you can sort an array into length(array) - length(longestIncreasingSubsequence(array)) move, moving only those elements that are not yet sorted in order.

If only the permitted operation is allowed by removing an element from index A and inserting it into index B, one element at a time, how would you create the correct moves to end the sorted array? Again, there must be the required length(array) - length(longestIncreasingSubsequence(array)) moves.

For example, here is an array:

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

The longest ascending subsequence:

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

The indices of these elements are:

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

So, the indexes we need to move are as follows:

 [ 1, 2, 6, 7] 

as these are indexes that are not yet sorted in order.

To get a sorted array, the final indices of these 4 elements:

 [ 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 rest of the elements are shifted, which makes the later move operations invalid. I tried to convert these indices, but still have not come up with the correct list of necessary moves. Any ideas?

I hope I have explained the problem well enough. Ask questions and I will clarify. Thanks!

Answer 1

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

Initial moves:

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

Step 1

Let the positions be transformed first, as if we first delete all the elements, and then insert the elements into new positions. For from positions, proceed on the left: delete at shift position 1 (2,6,7) to (1,5,6). Removing from 1 again shifts (5.6) to (4.5). A deletion of 5 replaces 5 to 4. For each position in from all subsequent positions with a greater or equal index should be reduced. We get:

 from: [ 1, 1, 4, 4] 

For to positions, proceed from the end: position 8 is correct. Position 2 is also correct, but this means that the previous (7.4) were actually (6.3) at the time of input. Therefore, we are correcting them. Similarly, an insert at 3 means that the previous position 6 was at position 5.

So, for the to array, we proceed from the end, for each position we reduce all previous positions with a large index. Array to becomes:

 to: [ 5, 3, 2, 8] 

Step 2

We have the right positions for 4 abstractions, followed by 4 inserts. Now we want to alternate between deletion and insertion.

Insert at 5 should be performed before deletion at (1, 1, 4). 5 is larger than any of them, so it will not affect the positions (1, 1, 4), but it affects 5 because 3 deletions are made to the left of the insertion point. 5 becomes 8.

An insert of 3 should appear before absorption (4, 4). Since 3 is less than 4, position 3 is independent of the deletion, but the deletion should be increased to positions (5, 5).

Insert on 2 goes to the last deletion at 5 (was 4). It is smaller, so 5 is set 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 arrays:

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

These are the final steps to perform with the correct positions while moving. The move can be read from left to right: Remove from 1, insert into 8. Remove from 1, insert into 3. Remove from 5, insert into 2. Remove from 6, insert into 8.