algorithm - The minimum number of "insertions" to sort an array

Question

Suppose there is an unordered list. The only operation we can do is to move an element and insert it back to any place. How many moves does it take to sort the whole list?

I guess the answer is size of the list - size of longest ordered sequence, but I have no idea how to prove it.

Answer 1

First note that moving an element doesn't change relative order of elements other than the one being moved.

Consider the longest non-decreasing subsequence (closely related to the longest increasing subsequence - the way to find them are similar).

By only moving the element not in this sequence, it's easy to see that we'd end up with a sorted list, since all the elements in this sequence are already sorted relative to each other.

If we don't move any elements in this sequence, any other element between two elements in this subsequence is guaranteed to be either greater than the larger element, or smaller than the smaller one (if this is not true, it itself would be in the longest sequence), so it needs to be moved.
(see below for example)

Does it need to be non-decreasing? Yes. Consider if two consecutive elements in this sequence are decreasing. In this case it would be impossible to sort the list without moving those two elements.

To minimize the number of moves required, it's sufficient to pick the longest sequence possible, as done above.

So the total number of moves required is the size of the list minus the size of the longest non-decreasing subsequence.

An example explaining the value of an element not in the non-decreasing subsequence mentioned above:

Consider the longest non-decreasing subsequence 1 x x 2 x x 2 x 4 (the x's are some elements not part of the sequence).

Now consider the possible values for an x between 2 and 4.

If it's 2, 3 or 4, the longest subsequence would include that element. If it's greater than 4 or smaller than 2, it needs to be moved.