Talk:Sorting algorithms/Pancake sort: Difference between revisions
(→Java algorithm: new section) |
|||
Line 50: | Line 50: | ||
The main idea is that instead of always sorting in order, we can sort in reverse order and do a flip to put back in correct order. Doing this costs one more flip than sorting in order. |
The main idea is that instead of always sorting in order, we can sort in reverse order and do a flip to put back in correct order. Doing this costs one more flip than sorting in order. |
||
Here are some cost values, expressed in flips: |
Here are some cost values to place the nth number, expressed in flips: |
||
<math>x_0 = maximum_{order} \rightarrow 1 flip</math>, same order |
<math>x_0 = maximum_{order} \rightarrow 1 flip</math>, same order |
Revision as of 23:26, 26 November 2010
Problem Instructions
Isn't the sequence 9 8 7 6 5 4 3 2 1 in descending order?
- Easily fixed with a single flip. -- Erik Siers 11:17, 26 November 2010 (UTC)
Burnt Pancake Problem
Why not include the "Burnt Pancake Problem" as a extra task? --<KJ> 08:53, 5 April 2010 (UTC)
- Mostly because I'm too lazy. ;-) I think it should be a separate task, or a subtask -- something like Sorting algorithms/Pancake sort/Burnt Pancake Problem. -- Eriksiers 13:38, 5 April 2010 (UTC)
Psychic RC'ers
Once again, I think to myself, "I should really do X," and someone else goes and does it almost the instant I think of it. This time it's the C implementation here. -- Erik Siers 20:46, 10 May 2010 (UTC)
J implementation
<lang J>flip=: C.~ C.@i.@- unsorted=: #~ 1 , [: >./\. 2 >/\ ] FlDown=: flip 1 + (i. >./)@unsorted FlipUp=: flip [:+/<./\@(<: {.)
pancake=: FlipUp@FlDown^:_</lang>
flip
reverses the first N items in a list
<lang J> 2 3 4 5 6 7 flip 3 4 3 2 5 6 7 </lang>
unsorted
finds the largest prefix where a number is less than a number to its left.
<lang J> unsorted 1 2 3 2 1 2 3 1 2 3 2 1</lang>
FlDown
finds the largest element in that unsorted prefix and uses flip to bring it to the front of the original list.
<lang J> FlDown 2 5 3 6 4 7 1 0 8 7 4 6 3 5 2 1 0 8</lang>
FlipUp
flips the first element of the list as far right as possible
<lang J> FlipUp 7 4 6 3 5 2 1 0 8 0 1 2 5 3 6 4 7 8</lang>
pancake
repeatedly uses FlipDown and then FlipUp until the result stops changing.
Java algorithm
Since we want to minimise the number of flips, I did a little cost analysis to see where we can win.
The main idea is that instead of always sorting in order, we can sort in reverse order and do a flip to put back in correct order. Doing this costs one more flip than sorting in order.
Here are some cost values to place the nth number, expressed in flips:
, same order
, same order
, same order
, reverse order
, reverse order
A good algorithm would analyse the cost for the few next steps of computation but the algorithm introduced here takes only one step of computation into account. A simple extension would be to note how many numbers will be sorted (cost 0) after next step.