Find the number of remove-then-append operations needed to sort a given array

Question

This is an interview question. A swap means removing any element from the array and appending it to the back of the same array. Given an array of integers, find the minimum number of swaps needed to sort the array.

Is there a solution better than O(n^2)?

For example:

Input array: [3124].

The number of swaps: 2 ([3124] -> [1243] -> [1234]).

Answer 1

The problem boils down to finding the longest prefix of the sorted array that appears as a subsequence in the input array. This determines the elements that do not need to be sorted. The remaining elements will need to be deleted one by one, from the smallest to the largest, and appended at the back.

In your example, [3, 1, 2, 4], the already-sorted subsequence is [1, 2]. The optimal solution is to delete the remaning two elements, 3 and 4, and append them at the back. Thus the optimal solution is two "swaps".

Finding the subsequence can be done in O(n logn) time using O(n) extra memory. The following pseudo-code will do it (the code also happens to be valid Python):

l = [1, 2, 4, 3, 99, 98, 7] s = sorted(l) si = 0 for item in l:   if item == s[si]:     si += 1 print len(l) - si 

If, as in your example, the array contains a permutation of integers from 1 to n, the problem can be solved in O(n) time using O(1) memory:

l = [1, 2, 3, 5, 4, 6] s = 1 for item in l:   if item == s:     s += 1 print len(l) - s + 1 

More generally, the second method can be used whenever we know the output array a priori and thus don't need to find it through sorting.

Answer 2

This might work in O(nlogn) even if we don't assume array of consecutive values.
If we do - it can be done in O(n). One way of doing it is with O(n) space and O(nlogn) time.
Given array A sort it (O(nlogn)) into a second array B.
now... (arrays are indexed from 1)

swaps = 0 b = 1 for a = 1 to len(A)   if A[a] == B[b]     b = b + 1   else     swaps = swaps + 1