Talk:Sorting algorithms/Pancake sort
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.