algorithm - Sort array in the minimum number of moves -

algorithm - Sort array in the minimum number of moves -

it theoretically possible sort array in length(array) - length(longestincreasingsubsequence(array)) moves moving elements not in sorted order.

if operation allowed in place move, removing element index , reinserting index b, 1 element @ time, how generate right moves end sorted array? again, there should length(array) - length(longestincreasingsubsequence(array)) moves required.

for example, here 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 elements are:

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

so, indices need move are:

[ 1, 2, 6, 7]

since indices not in sorted order.

in order end sorted array, final indices of 4 elements are:

[ 7, 4, 2, 8]

so, need simultaneously move index 1 index 7, index 2 index 4, index 6 index 2, , index 7 index 8. problem when element moved, other elements shifted around making later move operations invalid. i've tried transforming these indices, far have not come right list of moves required. ideas?

hopefully i've explained problem enough. please inquire questions , clarify. thanks!

your problem source positions expressed in prior order while destination positions in final order. when 1->7, don't know yet 7 in prior order. need create adjustments moves.

the original moves are:

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

let's first tranform positions if removing elements first, inserting elements @ new positions. from positions, proceed left: removing @ 1 shifts positions (2,6,7) downwards (1,5,6). removing @ 1 1 time again shifts (5,6) downwards (4,5). removing @ 5 shifts 5 downwards 4. every position in from subsequent positions larger or equal index must decremented. get:

from: [ 1, 1, 4, 4]

for to positions, proceed end: position 8 correct. position 2 correct, means prior (7,4) (6,3) @ time of insertion. adjust them. similarily, inserting @ 3 means prior position 6 @ 5.

so, to array, proceed end, every position decrement prior positions have larger index. to array becomes:

to: [ 5, 3, 2, 8]

what have right positions 4 removals followed 4 insertions. want interleave removals , insertions.

insertion @ 5 must done before removals @ (1, 1, 4). 5 larger of these, won't impact positions (1, 1, 4), 5 affected because 3 removals done left of insertion point. 5 becomes 8.

insertion @ 3 must come before removals @ (4, 4). since 3 smaller 4's, position 3 unaffected removals removals must incremented, positions (5, 5).

insertion @ 2 comes before lastly removal @ 5 (was 4). smaller, hence 5 adjusted 6.

general method:

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

we should arrays:

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

these final moves execute right positions @ time of move. moves can read left right: remove @ 1, insert @ 8. remove @ 1, insert @ 3. remove @ 5, insert @ 2. remove @ 6, insert @ 8.

arrays algorithm sorting