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)
Consecutive integers
Some of the solutions seem only to sort a set of consecutive integers (and indeed generate their test data by shuffling the integers 1..n). The task description requires the sorting of an 'array of integers' so shouldn't those restricted solutions be considered incorrect? RichardRussell 18:59, 15 November 2012 (UTC)
- Yes, I would like to see if the example programs will handle duplicate numbers as well. Also, some non-positive integers would be nice. -- Gerard Schildberger 19:39, 15 November 2012 (UTC)
J implementation
flip=: C.~ C.@i.@-
unsorted=: #~ 1 , [: >./\. 2 >/\ ]
FlDown=: flip 1 + (i. >./)@unsorted
FlipUp=: flip [:+/<./\@(<: {.)
pancake=: FlipUp@FlDown^:_
flip
reverses the first N items in a list
2 3 4 5 6 7 flip 3
4 3 2 5 6 7
unsorted
finds the largest prefix where a number is less than a number to its left.
unsorted 1 2 3 2 1 2 3
1 2 3 2 1
FlDown
finds the largest element in that unsorted prefix and uses flip to bring it to the front of the original list.
FlDown 2 5 3 6 4 7 1 0 8
7 4 6 3 5 2 1 0 8
FlipUp
flips the first element of the list as far right as possible
FlipUp 7 4 6 3 5 2 1 0 8
0 1 2 5 3 6 4 7 8
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.