How to sort a permutation by reversing subsequences (taken from Skiena 3rd ed.)

user_14669912 0
Viewed 351

I've been stuck on the second part of the following question from Skiena (The Algorithm Design Manual, 3rd ed.) for the past 24 hours and it's driving me nuts! I'm struggling to come up with new ideas at this point, and would appreciate some tips/solutions.

Exercise 4-27 Suppose you are given a permutation p of the integers 1 to n, and seek to sort them to be in increasing order [1, . . . , n]. The only operation at your disposal is reverse(p,i,j), which reverses the elements of a subsequence (p_i, ..., p_j) in the permutation. For the permutation [1, 4, 3, 2, 5] one reversal (of the second through fourth elements) suffices to sort.

  • Show that it is possible to sort any permutation using O(n) reversals.
  • Now suppose that the cost of reverse(p,i,j) is equal to its length, the number of elements in the range, |j − i| + 1. Design an algorithm that sorts p in O(nlog^2n) cost.

The first part appears fairly straightforward if we brute-force it: locate the position of the largest/smallest value and reverse the subsequence that will place it in the correct position. Repeat for the next largest/smallest value until the sequence is in the correct order. Clearly this requires n reversals at most.

But if I apply this brute-force approach to the second part of the question, it seems like the cost could be O(n^2) in the worst-case scenario. Anyone got any suggestions?

quicksort sorting algorithm
2 Answers

There is an algorithm for in-place merge sort that fits:

  1. Sort the beginning half of the array;
  2. Sort the last half of the array;
  3. Merge the two halves in-place.

The merge takes O(N log N) time:

  1. Determine the number of elements in the first half that belong in the second half;
  2. Swap those last elements in the first half with the first elements in the second half. You can do this with 3 reversals
  3. Recursively merge the 2 pieces in the first and last halves

Since merge takes O(N log N) time, the whole sort takes O(N log2 N) time.

user_54835260

I'm providing a few more notes to Matt Timmermans' excellent answer in case anyone needs more details (like I did) in the future.

Assume we have two sorted sequences a_1 < ... < a_n and b_1 < ... < b_n. We want to merge these two sequences into a single sorted sequence c_1 < ... < c_{2n}. We begin by finding the largest k such that b_1, ..., b_k are among the n smallest values in the final sorted set. We can do this in O(2n). By symmetry, a_{n-k+1}, ..., a_n must be among the n largest values in the final sorted set.

We can use the reverse operation to swap a_{n-k+1}, ..., a_n and b_1, ..., b_k with cost O(2k). We now have 4 sequences: a_1 < ... < a_{n-k}, b_k > ... > b_1, a_n > ... > a_{n-k+1} and b_{k+1} < ... < b_n. The sequences b_k, ..., b_1 and a_n, ..., a_{n-k+1} are in reverse order due to the original reverse operation. Hence we apply another reverse operation to both sequences to order them correctly. This has cost O(2k).

We have now halved size of our original problem with cost ~ O(n). Our reduced problem is to merge the ordered sequences a_1 < ... < a_{n-k} and b_1 < ... < b_k, and also to merge the ordered sequences a_{n-k+1} < ... < a_n and b_{k+1} < ... < b_n. The sequence bookkeeping gets a little hairy at this point but it's helpful to think about the special situation of k=n/2 to get a feeling for the general approach.

For k=n/2, we have an identical situation as our original problem (two sorted sequences of equal size), except we now have two pairs of sequences, each with half the length of our original problem. So we can repeat our approach for the original problem on these new pairs of sequences. This will again split the size of our problem in two with cost 2O(n/2). In general, for 2^m pairs of ordered sequences of length n/2^m, the cost will be 2^m O(n/2^m) i.e. O(n).

By repeatedly splitting our problem by a factor of 2 and at a cost of O(n) for each split, we see that this recursive approach will allow us to merge our original sequences with cost at most O(n logn).

Thus we can merge two ordered sequences of length n using the reverse operation with cost at most O(n logn). By applying another recursive approach (like in traditional sorting algorithms) we find that we can sort arbitrarily ordered sequences in O(n log^2n).

user_146699120
Related