w3hello.com logo
Home PHP C# C++ Android Java Javascript Python IOS SQL HTML videos Categories
Sort array in the minimum number of moves

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]

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]

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 i = 0 to size-1
    for j = size-1 to i+1
        if from[j] < to[i] then increment to[i]
        else decrement 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.

© Copyright 2018 w3hello.com Publishing Limited. All rights reserved.