Talk:Sorting algorithms/Pancake sort: Difference between revisions
No edit summary |
|||
Line 1: | Line 1: | ||
== Problem Instructions == |
|||
Isn't the sequence 9 8 7 6 5 4 3 2 1 in descending order? |
|||
== Burnt Pancake Problem == |
|||
Why not include the "Burnt Pancake Problem" as a extra task? --[[User:Jofur|<KJ>]] 08:53, 5 April 2010 (UTC) |
Why not include the "Burnt Pancake Problem" as a extra task? --[[User:Jofur|<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'''. -- [[User:Eriksiers|Eriksiers]] 13:38, 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'''. -- [[User:Eriksiers|Eriksiers]] 13:38, 5 April 2010 (UTC) |
Revision as of 11:09, 26 November 2010
Problem Instructions
Isn't the sequence 9 8 7 6 5 4 3 2 1 in descending order?
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.