Talk:Sorting algorithms/Pancake sort: Difference between revisions
(→Psychic RC'ers: new section) |
(→J implementation: new section) |
||
Line 5: | Line 5: | ||
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. -- [[User:Eriksiers|Erik Siers]] 20:46, 10 May 2010 (UTC) |
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. -- [[User:Eriksiers|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> |
|||
<code>flip</code> 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> |
|||
<code>unsorted</code> finds the largest prefix where a number is less than a number to its left. |
|||
<lang J> unsorted 3 2 1 2 3 |
|||
3 2 1</lang> |
|||
<code>FlDown</code> finds the largest element in that unsorted prefix and brings it to the front. |
|||
<lang J> FlDown 2 5 3 6 4 7 1 0 8 |
|||
7 4 6 3 5 2 1 0 8</lang> |
|||
<code>FlipUp</code> 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> |
|||
<code>pancake</code> repeatedly uses FlipDown and then FlipUp until the result stops changing. |
Revision as of 15:00, 19 May 2010
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 3 2 1 2 3 3 2 1</lang>
FlDown
finds the largest element in that unsorted prefix and brings it to the front.
<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.