tfgs's blog

Minimum number of relocation to sort array
By tfgs, history, 11 months ago, In English

Hello, from this problem I know that the minimum number of relocations to sort the array is N-(length of longest non-dec subsequence). Please, can you help me prove this result?

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

proof by ac:)

→ Reply
»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

The principle behind this is pretty similar to insertion sort's: first consider a sorted subsequence of the array. Then, for every element not in this subsequence, relocate them into their correct position in the array. Therefore, the minimum number of relocations one has to do is equal to the number of out-of-place elements.

For instance, take the array 3, 1, 5, 2, 4 for example, take 3, 5 to be the sorted subsequence (this isn't the optimal solution — for demonstrational purposes only!)

3 1 5 2 4 → 1 3 5 2 4 → 1 2 3 5 4 → 1 2 3 4 5

This would take 3 steps: N — length of sorted subsequence. Bolded elements denote sorted elements. Note that the initial positions of the unsorted elements don't matter — they will be relocated anyways.

Naturally, since we want to minimise the number of relocations, we would want to take the longest nondecreasing subsequence as the initial sorted subsequence. Therefore, the answer to this problem is indeed N minus the length of the longest non-dec subsequence.

→ Reply