Everyone here's mentioned O(n^2) Pancake sorting. Here's a solution in O(n
log n)
A run is defined as a sequence of consecutive values in the array.
1. Go through the array and reverse descending runs - O(n) as reverse(i, j)
is supplied. Now you have an array with many runs in ascending order. It
looks something like a0, a1 ... ak, b0, b1, ... bl, c0, c1, ... cm ...
2. Perform a merge procedure pairwise for consecutive runs in the array. The
merge is performed as follows:
If a0, a1, a2 ...ak b0, b1, b2... bl are consecutive runs, then:
a) Compare a0, b0 (using get() operation to get the values).
--- Else If b0 < a0 then perform step (b).
--- Else a0 is in its correct place, increment pointer to the 'a' array
and repeat step 2 for a1... ak, b0 ... bl
b) reverse(a0 ... b0) and then reverse (ak ... a0) - giving b0, a0, a1 ...
ak, b1, b2 .. bl. Repeat step 2 for the run a0, a1 ... ak, b1, b2 ... bl
Complexity analysis:
Step 1 can be done in O(n) time. Using 2 indices to locate boundaries of
runs and an O(1) reverse call, this is easy to achieve.
Step 2 The merge procedure requires 2 get() operations (one of which may be
optimized away with careful coding) and (in the worst case) 2 reverse(i,j)
operations. Therefore, the cost of putting 1 element in its correct position
is O(1). Hence 2 sequences of lengths n and m can be merged in O(min{n, m})
time.
Overall complexity:
Let us assume that we end up with K runs of lengths L1 - Lk from step 1.
Cost of this step O(N)
Cost of merging adjacent runs = O(min{Li, Li+1}) = O(length of run)
Total number of merges that will take place = K
This is similar to mergesort and you can go ahead and prove that the
complexity is going to be of the order O( n log n ).
---
DK
http://twitter.com/divyekapoor
http://www.divye.in
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/IxTQlwpStSIJ.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
