Paratha Sorting: Simple version

[Akhil Bhiwal]

One fine day, you enter into kitchen and see your mother making
parathas. Your mother makes parathas in perfect circular shape and
puts them on top of each other such that parathas form a stack. All
parathas in the stack are of varying diameter.

Now you have to sort the parathas such that the largest paratha is at
bottom and smallest at the top of stack. The only way you can sort is:
You can insert a spoon between parathas and flip them. For eg: if you
insert spoon below paratha 4 (from top) and flip it then the new order
of paratha will be 4 3 2 1 5 6 ...

Find an optimized solution for this problem. Also tell the runtime of
your algorithm.



P.S.: This post is dedicated to my mom who makes tasty parathas. Today
is mother's day.

[Satish Eerpini]

isn't this a desi version of the Towers of Hanoi problem ?? (just a
guess from the first look of it )
nice interpretation ... :)


Cheers
Satish

--
http://tuxitter.blogspot.com

[Mickey]

Yeah it has resemblance with the towers of Hanoi but there are
differences too: the parathas are not ordered to begin with and we
have only one peg.

Let us have N parathas. Position 1 is the top (smallest paratha).

Here is a possible approach:

for(i = N; i > 1; --i)
{ find the paratha P that should be at position i.
if(P is at position i)
{ continue;
}
else
{ put your spoon below P and flip the stack.
// Now this deserving paratha is on top.
Now put your spoon below position i and flip the stack once again.
// Our big paratha P is in its due place now.
}
}

we have to find the complexity of these two operations:
1. find the paratha P that should be at position i.
Say I use simple linear search to find this paratha P. I will have to
look at i paratha each time. Considering the loop total time will be
O(N*N). Space complexity is amortized. To be precise the worst case is
N(N-1)/2.

2. flip after putting spoon below paratha i.
This involved i/2 swaps in memory, considering that I used an
array(with random access) instead of a true stack (Yeah I am cheating
here... you can't do this swapping with real parathas). considering
swap as elementary function the time taken in worst case would be
N(N-1)/4. This is also O(N*N). Space complexity is amortized.

And for both of these the average case would also be the same and
these two time complexities ought to be added. That gives me still
O(N*N). Now... that sounds much cheaper than Towers of Hanoi. Time
complexity of solving Towers of Hanoi with N discs would be O(a^N)
where a is a constant greater than 1. (Don't ask me to prove the time
complexity of Towers of Hanoi... and about a journal paper that says
that it can be done in O(n)).

Is there a data structure that can be used to make these operations
faster at the expense of increased space usage?

Regards,
Jyoti

[Akhil Bhiwal]

This algorithm will work fine with given space and time complexity.

No idea about any other data structure.