Talk:Sorting algorithms/Pancake sort: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎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.

Retrieved from "https://rosettacode.org/wiki/Talk:Sorting_algorithms/Pancake_sort?oldid=145308"