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.
On a closer look, you can clearly see that as per my approach to the
problem, I have defined something similar to the swap(i, j) operator.
Given this operator, you can implement any O(n log n) sort that you desire.
swap(i, j) = reverse(i + 1, j), reverse(i, i + 1), reverse(i+1, j)
Have fun
Oops, there's a bug in my analysis! the sort complexity is even better at
O(N) :)
If you're doing K merges of subarrays of size O( N / K ) (which is the
worst case for this algo due to the merge cost of O(min{N, M}) ) using the
reverse operation you've supplied, the result is an O(N) sort
Really really sorry for polluting this thread, but there's small issue in
that analysis:
The cost O(N) is in terms of reverse operations executed (that is swaps) and
not in terms of the number of comparisons. The number of comparisons remain
O(N log N) but the maximum number of swaps is O(N)
There is an array in an external system (i.e. u cannot access the
array elements directly).
The system exposes 3 functions of O(1) - (assume) :
length() - returns the length of the array.
get(i) - returns the element at index i.
reverse(i,j) - reverses the elements in the array from index i to
@rossI have a doubt regarding reverse function...
does it rotate the array or reverse it??
for say it is 12345
reverse(0,4) make it 51234 or 54321???
On 6/12/11, ross jagadish1...@gmail.com wrote:
There is an array in an external system (i.e. u cannot access the
array elements directly).
