Sorting algorithms/Pancake sort: Difference between revisions
(Add NetRexx implementation) |
|||
Line 1,706: | Line 1,706: | ||
def pancake_sort! |
def pancake_sort! |
||
num_flips = 0 |
num_flips = 0 |
||
self.size.downto( |
(self.size-1).downto(1) do |end_idx| |
||
max = self[0..end_idx].max |
|||
max_idx = self[0..end_idx]. |
max_idx = self[0..end_idx].index(max) |
||
next if max_idx == end_idx |
next if max_idx == end_idx |
||
⚫ | |||
if max_idx > 0 |
if max_idx > 0 |
||
self[0..max_idx] = self[0..max_idx].reverse |
self[0..max_idx] = self[0..max_idx].reverse |
||
⚫ | |||
⚫ | |||
num_flips += 1 |
|||
p [num_flips, self] |
|||
end |
|||
end |
end |
||
⚫ | |||
self[0..end_idx] = self[0..end_idx].reverse |
self[0..end_idx] = self[0..end_idx].reverse |
||
⚫ | |||
if $DEBUG |
|||
num_flips += 1 |
|||
⚫ | |||
⚫ | |||
end |
end |
||
self |
self |
||
end |
end |
||
Line 1,735: | Line 1,726: | ||
p a.pancake_sort!</lang> |
p a.pancake_sort!</lang> |
||
sample output: |
'''sample output:''' |
||
<pre>$ ruby -d sorting_pancake.rb |
<pre>$ ruby -d sorting_pancake.rb |
||
[7, 3, 6, 8, 2, 4, 5, 1, 9] |
[7, 3, 6, 8, 2, 4, 5, 1, 9] |
Revision as of 18:41, 13 May 2013
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
Sort an array of integers (of any convenient size) into ascending order using Pancake sorting. In short, instead of individual elements being sorted, the only operation allowed is to "flip" one end of the list, like so:
Before: 6 7 8 9 2 5 3 4 1 After: 9 8 7 6 2 5 3 4 1
Only one end of the list can be flipped; this should be the low end, but the high end is okay if it's easier to code or works better, but it must be the same end for the entire solution. (The end flipped can't be arbitrarily changed.)
Show both the initial, unsorted list and the final sorted list. (Intermediate steps during sorting are optional.) Optimizations are optional (but recommended).
For more information on pancake sorting, see the Wikipedia entry.
See also:
Ada
<lang Ada>with Ada.Text_IO; procedure Pancake_Sort is
generic type Element_Type is private; type Index_Type is range <>; type Array_Type is array (Index_Type range <>) of Element_Type; with function ">" (Left, Right : Element_Type) return Boolean is <>; procedure Pancake_Sort (Data: in out Array_Type);
procedure Pancake_Sort (Data: in out Array_Type) is procedure Flip (Up_To : in Index_Type) is Temp : constant Array_Type := Data (Data'First .. Up_To); begin for I in Temp'Range loop Data (I) := Temp (Temp'First + Up_To - I); end loop; end Flip; Max_Index : Index_Type; begin for I in reverse Data'First + 1 .. Data'Last loop Max_Index := Data'First; for A in Data'First + 1 .. I loop if Data(A) > Data (Max_Index) then Max_Index := A; end if; end loop; if Max_Index /= I then if Max_Index > Data'First then Flip (Max_Index); end if; Flip (I); end if; end loop; end Pancake_Sort;
type Integer_Array is array (Positive range <>) of Integer; procedure Int_Pancake_Sort is new Pancake_Sort (Integer, Positive, Integer_Array); Test_Array : Integer_Array := (3, 14, 1, 5, 9, 2, 6, 3);
begin
Int_Pancake_Sort (Test_Array); for I in Test_Array'Range loop Ada.Text_IO.Put (Integer'Image (Test_Array (I))); end loop; Ada.Text_IO.New_Line;
end Pancake_Sort;</lang>
Output:
1 2 3 3 5 6 9 14
AutoHotkey
<lang autohotkey>;--------------------------------------------------------------------------- Loop { ; test loop
- ---------------------------------------------------------------------------
Loop, % Data0 := 10 Random, Data%A_Index%, 10, 99 Unsorted := Array2List("Data") PancakeSort("Data") Sorted := Array2List("Data") MsgBox, 1, Pancake Sort, %Unsorted%`n%Sorted% IfMsgBox, Cancel, Break
}
- ---------------------------------------------------------------------------
PancakeSort(Array) { ; implementation of pancake sort algorithm
- ---------------------------------------------------------------------------
Loop, % %Array%0 - 1 { m := 0 Loop, % s := %Array%0 - A_Index + 1 If (m <= %Array%%A_Index%) m := %Array%%A_Index%, p := A_Index If (p < s) && (p > 1) Flip(Array, p) If (p < s) Flip(Array, s) }
}
- ---------------------------------------------------------------------------
Flip(Array, n) { ; flip the first n members of Array
- ---------------------------------------------------------------------------
Loop, % x := n // 2 { i := n - A_Index + 1 %Array%%i% := (%Array%%A_Index% "", %Array%%A_Index% := %Array%%i%) }
}
- ---------------------------------------------------------------------------
Array2List(Array) { ; returns a space separated list from an array
- ---------------------------------------------------------------------------
Loop, % %Array%0 List .= (A_Index = 1 ? "" : " ") %Array%%A_Index% Return, List
} </lang>
BASIC
Text
<lang qbasic>RANDOMIZE TIMER
DIM nums(9) AS INTEGER DIM L0 AS INTEGER, L1 AS INTEGER, n AS INTEGER
'initial values FOR L0 = 0 TO 9
nums(L0) = L0
NEXT 'scramble FOR L0 = 9 TO 1 STEP -1
n = INT(RND * (L0)) + 1 IF n <> L0 THEN SWAP nums(n), nums(L0)
NEXT 'display initial condition FOR L0 = 0 TO 9
PRINT nums(L0);
NEXT PRINT
FOR L1 = 9 TO 1 STEP -1
n = 0 FOR L0 = 1 TO L1 IF nums(n) < nums(L0) THEN n = L0 NEXT
IF (n < L1) THEN IF (n > 0) THEN FOR L0 = 0 TO (n \ 2) SWAP nums(L0), nums(n - L0) NEXT FOR L0 = 0 TO 9 PRINT nums(L0); NEXT PRINT END IF FOR L0 = 0 TO (L1 \ 2) SWAP nums(L0), nums(L1 - L0) NEXT
FOR L0 = 0 TO 9 PRINT nums(L0); NEXT PRINT END IF
NEXT</lang>
Sample output:
0 4 6 1 8 7 2 5 3 9 8 1 6 4 0 7 2 5 3 9 3 5 2 7 0 4 6 1 8 9 7 2 5 3 0 4 6 1 8 9 1 6 4 0 3 5 2 7 8 9 6 1 4 0 3 5 2 7 8 9 2 5 3 0 4 1 6 7 8 9 5 2 3 0 4 1 6 7 8 9 1 4 0 3 2 5 6 7 8 9 4 1 0 3 2 5 6 7 8 9 2 3 0 1 4 5 6 7 8 9 3 2 0 1 4 5 6 7 8 9 1 0 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
Graphics
This is a graphical variation of the above.
<lang qbasic>RANDOMIZE TIMER
CONST delay = .1 'controls display speed
DIM nums(14) AS INTEGER DIM L0 AS INTEGER, L1 AS INTEGER, n AS INTEGER, ttmp AS SINGLE
'initial values FOR L0 = 0 TO 14
nums(L0) = L0
NEXT 'scramble FOR L0 = 14 TO 1 STEP -1
n = INT(RND * (L0)) + 1 IF n <> L0 THEN SWAP nums(n), nums(L0)
NEXT
'display initial condition CLS GOSUB displayer
FOR L1 = 14 TO 1 STEP -1
n = 0 FOR L0 = 1 TO L1 IF nums(n) < nums(L0) THEN n = L0 NEXT
IF (n < L1) THEN IF (n > 0) THEN FOR L0 = 0 TO (n \ 2) SWAP nums(L0), nums(n - L0) NEXT GOSUB displayer END IF FOR L0 = 0 TO (L1 \ 2) SWAP nums(L0), nums(L1 - L0) NEXT
GOSUB displayer END IF
NEXT
COLOR 7 END
displayer:
LOCATE 1, 1 FOR L0 = 0 TO 14 COLOR nums(L0) + 1 IF nums(L0) < 10 THEN PRINT " "; PRINT RTRIM$(LTRIM$(STR$(nums(L0)))); STRING$(nums(L0), 219); SPACE$(20) NEXT ttmp = TIMER DO WHILE TIMER < ttmp + delay: LOOP RETURN</lang>
Sample output:
BBC BASIC
<lang bbcbasic> DIM test(9)
test() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1 PROCpancakesort(test()) FOR i% = 0 TO 9 PRINT test(i%) ; NEXT PRINT END DEF PROCpancakesort(a()) LOCAL i%, j%, m% FOR i% = DIM(a(),1)+1 TO 2 STEP -1 m% = 0 FOR j% = 1 TO i%-1 IF a(j%) > a(m%) m% = j% NEXT m% += 1 IF m% < i% THEN IF m% > 1 PROCflip(a(), m%) PROCflip(a(), i%) ENDIF NEXT ENDPROC DEF PROCflip(a(), n%) IF n% < 2 ENDPROC LOCAL i% n% -= 1 FOR i% = 0 TO n% DIV 2 SWAP a(i%), a(n%-i%) NEXT ENDPROC</lang>
Output:
-31 0 1 2 2 4 65 83 99 782
C
The function that sorts: <lang c>int pancake_sort(int *list, unsigned int length) {
//If it's less than 2 long, just return it as sorting isn't really needed... if(length<2) return 0;
int i,a,max_num_pos,moves; moves=0;
for(i=length;i>1;i--) { //Find position of the max number in pos(0) to pos(i) max_num_pos=0; for(a=0;a<i;a++) { if(list[a]>list[max_num_pos]) max_num_pos=a; }
if(max_num_pos==i-1) //It's where it need to be, skip continue;
//Get the found max number to the beginning of the list (unless it already is) if(max_num_pos) { moves++; do_flip(list, length, max_num_pos+1); }
//And then move it to the end of the range we're working with (pos(0) to pos(i)) moves++; do_flip(list, length, i);
//Then everything above list[i-1] is sorted and don't need to be touched
}
return moves;
}</lang>
Where do_flip() is a simple function to flip a part of an array: <lang c>void do_flip(int *list, int length, int num) {
int swap; int i=0; for(i;i<--num;i++) { swap=list[i]; list[i]=list[num]; list[num]=swap; }
}</lang>
Testing the function: <lang c>int main(int argc, char **argv) {
//Just need some random numbers. I chose <100 int list[9]; int i; srand(time(NULL)); for(i=0;i<9;i++) list[i]=rand()%100;
//Print list, run code and print it again displaying number of moves printf("\nOriginal: "); print_array(list, 9);
int moves = pancake_sort(list, 9, 1);
printf("\nSorted: "); print_array(list, 9); printf(" - with a total of %d moves\n", moves);
}</lang>
C++
<lang c>#include <algorithm>
- include <iostream>
- include <iterator>
- include <vector>
// pancake sort template (calls predicate to determine order) template <typename BidIt, typename Pred> void pancake_sort(BidIt first, BidIt last, Pred order) {
if (std::distance(first, last) < 2) return; // no sort needed
for (; first != last; --last) { BidIt mid = std::max_element(first, last, order); if (mid == last - 1) { continue; // no flips needed } if (first != mid) { std::reverse(first, mid + 1); // flip element to front } std::reverse(first, last); // flip front to final position }
}
// pancake sort template (ascending order) template <typename BidIt> void pancake_sort(BidIt first, BidIt last) {
pancake_sort(first, last, std::less<typename std::iterator_traits<BidIt>::value_type>());
}
int main() {
std::vector<int> data; for (int i = 0; i < 20; ++i) { data.push_back(i); // generate test data } std::random_shuffle(data.begin(), data.end()); // scramble data
std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << "\n";
pancake_sort(data.begin(), data.end()); // ascending pancake sort
std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << "\n";
}</lang>Output:
4 10 11 15 14 16 17 1 6 9 3 7 19 2 0 12 5 18 13 8 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
C#
<lang C sharp|C#> public static class PancakeSorter {
public static void Sort<T>(List<T> list) where T : IComparable { if (list.Count < 2) { return; } int i, a, max_num_pos; for (i = list.Count; i > 1; i--) { max_num_pos = 0; for (a = 0; a < i; a++) { if (list[a].CompareTo(list[max_num_pos]) > 0) { max_num_pos = a; } } if (max_num_pos == i - 1) { continue; } if (max_num_pos > 0) { Flip(list, list.Count, max_num_pos + 1); } Flip(list, list.Count, i); } return; } private static void Flip<T>(List<T> list, int length, int num) { for (int i = 0; i < --num; i++) { T swap = list[i]; list[i] = list[num]; list[num] = swap; } }
} </lang>
Common Lisp
<lang lisp>(defun pancake-sort (seq)
"A destructive version of Pancake Sort that works with either lists or arrays of numbers." (defun flip (lst index) (setf (subseq lst 0 index) (reverse (subseq lst 0 index)))) (loop with lst = (coerce seq 'list)
for i from (length lst) downto 2 for index = (position (apply #'max (subseq lst 0 i)) lst) do (unless (= index 0) (flip lst (1+ index))) (flip lst i) finally (return (coerce lst (type-of seq)))))</lang> Output: <lang lisp>CL-USER> (pancake-sort '(6 7 8 9 2 5 3 4 1)) ;list (1 2 3 4 5 6 7 8 9) CL-USER> (pancake-sort #(6 7 8 9 2 5 3 4 1)) ;array
- (1 2 3 4 5 6 7 8 9)
CL-USER> (pancake-sort #(6.5 7.5 8 9 2 5 3 4 1.0)) ;array with integer and floating point values
- (1.0 2 3 4 5 6.5 7.5 8 9)</lang>
D
<lang d>import std.stdio, std.algorithm;
void pancakeSort(bool tutor=false, T)(T[] data) {
foreach_reverse (i; 2 .. data.length + 1) { immutable maxIndex = i - data[0 .. i].minPos!q{a > b}().length; if (maxIndex + 1 != i) { if (maxIndex != 0) { static if (tutor) writeln("With: ", data, " doflip ", maxIndex + 1); data[0 .. maxIndex + 1].reverse(); }
static if (tutor) writeln("With: ", data, " doflip ", i); data[0 .. i].reverse(); } }
}
void main() {
char[] data = "769248135".dup; pancakeSort!true(data); writeln(data);
}</lang>
- Output:
With: 769248135 doflip 3 With: 967248135 doflip 9 With: 531842769 doflip 4 With: 813542769 doflip 8 With: 672453189 doflip 2 With: 762453189 doflip 7 With: 135426789 doflip 3 With: 531426789 doflip 5 With: 241356789 doflip 2 With: 421356789 doflip 4 With: 312456789 doflip 3 With: 213456789 doflip 2 123456789
Euphoria
<lang euphoria>function flip(sequence s, integer n)
object temp for i = 1 to n/2 do temp = s[i] s[i] = s[n-i+1] s[n-i+1] = temp end for return s
end function
function pancake_sort(sequence s)
integer m for i = length(s) to 2 by -1 do m = 1 for j = 2 to i do if compare(s[j], s[m]) > 0 then m = j end if end for if m < i then if m > 1 then s = flip(s,m) end if s = flip(s,i) end if end for return s
end function
constant s = rand(repeat(100,10))
? s ? pancake_sort(s)</lang>
Output:
{24,32,100,15,8,34,50,79,46,52} {8,15,24,32,34,46,50,52,79,100}
F#
<lang fsharp>open System
let show data = data |> Array.iter (printf "%d ") ; printfn "" let split (data: int[]) pos = data.[0..pos], data.[(pos+1)..]
let flip items pos =
let lower, upper = split items pos Array.append (Array.rev lower) upper
let pancakeSort items =
let rec loop data limit = if limit <= 0 then data else let lower, upper = split data limit let indexOfMax = lower |> Array.findIndex ((=) (Array.max lower)) let partialSort = Array.append (flip lower indexOfMax |> Array.rev) upper loop partialSort (limit-1)
loop items ((Array.length items)-1)</lang>
Usage: pancakeSort [|31; 41; 59; 26; 53; 58; 97; 93; 23; 84|] |> show
Output:
23 26 31 41 53 58 59 84 93 97
Fortran
<lang fortran>program Pancake_Demo
implicit none integer :: list(8) = (/ 1, 4, 7, 2, 5, 8, 3, 6 /) call Pancake_sort(list)
contains
subroutine Pancake_sort(a)
integer, intent(in out) :: a(:) integer :: i, maxpos write(*,*) a do i = size(a), 2, -1
! Find position of max number between index 1 and i
maxpos = maxloc(a(1:i), 1)
! is it in the correct position already?
if (maxpos == i) cycle
! is it at the beginning of the array? If not flip array section so it is
if (maxpos /= 1) then a(1:maxpos) = a(maxpos:1:-1) write(*,*) a end if
! Flip array section to get max number to correct position
a(1:i) = a(i:1:-1) write(*,*) a end do
end subroutine
end program Pancake_Demo</lang> Output:
1 4 7 2 5 8 3 6 8 5 2 7 4 1 3 6 6 3 1 4 7 2 5 8 7 4 1 3 6 2 5 8 5 2 6 3 1 4 7 8 6 2 5 3 1 4 7 8 4 1 3 5 2 6 7 8 5 3 1 4 2 6 7 8 2 4 1 3 5 6 7 8 4 2 1 3 5 6 7 8 3 1 2 4 5 6 7 8 2 1 3 4 5 6 7 8 1 2 3 4 5 6 7 8
Go
<lang go>package main
import "fmt"
func main() {
list := pancake{31, 41, 59, 26, 53, 58, 97, 93, 23, 84} fmt.Println("unsorted:", list)
list.sort() fmt.Println("sorted! ", list)
}
type pancake []int
func (a pancake) sort() {
for uns := len(a) - 1; uns > 0; uns-- { // find largest in unsorted range lx, lg := 0, a[0] for i := 1; i <= uns; i++ { if a[i] > lg { lx, lg = i, a[i] } } // move to final position in two flips a.flip(lx) a.flip(uns) }
}
func (a pancake) flip(r int) {
for l := 0; l < r; l, r = l+1, r-1 { a[l], a[r] = a[r], a[l] }
}</lang> Output:
unsorted: [31 41 59 26 53 58 97 93 23 84] sorted! [23 26 31 41 53 58 59 84 93 97]
Groovy
This formulation of the pancake sort achieves stability by picking the last index (rather than, say, the first) in the remaining sublist that matches the max value of the remaining sublist. Performance is enhanced somewhat by not flipping if the flipPoint is already at the end of the remaining sublist. <lang groovy>def makeSwap = { a, i, j = i+1 -> print "."; aj,i = ai,j }
def flip = { list, n -> (0..<((n+1)/2)).each { makeSwap(list, it, n-it) } }
def pancakeSort = { list ->
def n = list.size() (1..<n).reverse().each { i -> def max = list[0..i].max() def flipPoint = (i..0).find{ list[it] == max } if (flipPoint != i) { flip(list, flipPoint) flip(list, i) } } list
}</lang>
Test: <lang groovy>println (pancakeSort([23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4])) println (pancakeSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1])) println () println (pancakeSort([10, 10.0, 10.00, 1])) println (pancakeSort([10, 10.00, 10.0, 1])) println (pancakeSort([10.0, 10, 10.00, 1])) println (pancakeSort([10.0, 10.00, 10, 1])) println (pancakeSort([10.00, 10, 10.0, 1])) println (pancakeSort([10.00, 10.0, 10, 1]))</lang> The use of decimals and integers that compare as equal demonstrates, but of course not prove, that the sort is stable.
Output:
..........................................................................................................................................[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99] ............................................................................................................................................................................................................[0, 1, 4, 5, 7, 8, 12, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88] ...[1, 10, 10.0, 10.00] ...[1, 10, 10.00, 10.0] ...[1, 10.0, 10, 10.00] ...[1, 10.0, 10.00, 10] ...[1, 10.00, 10, 10.0] ...[1, 10.00, 10.0, 10]
Haskell
<lang haskell>import Data.List import Control.Arrow import Control.Monad import Data.Maybe
dblflipIt :: (Ord a) => [a] -> [a] dblflipIt = uncurry ((reverse.).(++)). first reverse
. ap (flip splitAt) (succ. fromJust. (elemIndex =<< maximum))
dopancakeSort :: (Ord a) => [a] -> [a] dopancakeSort xs = dopcs (xs,[]) where
dopcs ([],rs) = rs dopcs ([x],rs) = x:rs dopcs (xs,rs) = dopcs $ (init &&& (:rs).last ) $ dblflipIt xs</lang>
Example: <lang haskell>*Main> dopancakeSort [3,2,1,0,2] [0,1,2,2,3]</lang>
Icon and Unicon
<lang Icon>procedure main() #: demonstrate various ways to sort a list and string
demosort(pancakesort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty") pancakeflip := pancakeflipshow # replace pancakeflip procedure with a variant that displays each flip pancakesort([3, 14, 1, 5, 9, 2, 6, 3])
end
procedure pancakesort(X,op) #: return sorted list ascending(or descending) local i,m
op := sortop(op,X) # select how and what we sort
every i := *X to 2 by -1 do { # work back to front m := 1 every j := 2 to i do if op(X[m],X[j]) then m := j # find X that belongs @i high (or low) if i ~= m then { # not already in-place X := pancakeflip(X,m) # . bring max (min) to front X := pancakeflip(X,i) # . unsorted portion of stack } } return X
end
procedure pancakeflip(X,tail) #: return X[1:tail] flipped local i
i := 0 tail := integer(\tail|*X) + 1 | runerr(101,tail) while X[(i +:= 1) < (tail -:= 1)] :=: X[i] # flip return X
end
procedure pancakeflipshow(X,tail) #: return X[1:tail] flipped (and display) local i
i := 0 tail := integer(\tail|*X) + 1 | runerr(101,tail) while X[(i +:= 1) < (tail -:= 1)] :=: X[i] # flip every writes(" ["|right(!X,4)|" ]\n") # show X return X
end</lang>
Note: This example relies on the supporting procedures 'sortop', and 'demosort' in Bubble Sort. The full demosort exercises the named sort of a list with op = "numeric", "string", ">>" (lexically gt, descending),">" (numerically gt, descending), a custom comparator, and also a string.
Abbreviated sample output:
Sorting Demo using procedure pancakesort on list : [ 3 14 1 5 9 2 6 3 ] with op = &null: [ 1 2 3 3 5 6 9 14 ] (0 ms) ... on string : "qwerty" with op = &null: "eqrtwy" (0 ms)
The output below shows the flipping:
[ 14 3 1 5 9 2 6 3 ] [ 3 6 2 9 5 1 3 14 ] [ 9 2 6 3 5 1 3 14 ] [ 3 1 5 3 6 2 9 14 ] [ 6 3 5 1 3 2 9 14 ] [ 2 3 1 5 3 6 9 14 ] [ 5 1 3 2 3 6 9 14 ] [ 3 2 3 1 5 6 9 14 ] [ 3 2 3 1 5 6 9 14 ] [ 1 3 2 3 5 6 9 14 ] [ 3 1 2 3 5 6 9 14 ] [ 2 1 3 3 5 6 9 14 ] [ 2 1 3 3 5 6 9 14 ] [ 1 2 3 3 5 6 9 14 ]
J
<lang J>flip=: C.~ C.@i.@- unsorted=: #~ 1 , [: >./\. 2 >/\ ] FlDown=: flip 1 + (i. >./)@unsorted FlipUp=: flip 1 >. [:+/>./\&|.@(< {.)
pancake=: FlipUp@FlDown^:_</lang>
Example use:
<lang J> (,:pancake) ?~9 1 0 8 7 4 6 3 5 2 0 1 2 3 4 5 6 7 8</lang>
See the discussion page for illustrations of the other words.
Java
<lang java> public class PancakeSort {
int[] heap;
public String toString() { String info = ""; for (int x: heap) info += x + " "; return info; } public void flip(int n) { for (int i = 0; i < (n+1) / 2; ++i) { int tmp = heap[i]; heap[i] = heap[n-i]; heap[n-i] = tmp; } System.out.println("flip(0.." + n + "): " + toString()); } public int[] minmax(int n) { int xm, xM; xm = xM = heap[0]; int posm = 0, posM = 0; for (int i = 1; i < n; ++i) { if (heap[i] < xm) { xm = heap[i]; posm = i; } else if (heap[i] > xM) { xM = heap[i]; posM = i; } } return new int[] {posm, posM}; } public void sort(int n, int dir) { if (n == 0) return; int[] mM = minmax(n); int bestXPos = mM[dir]; int altXPos = mM[1-dir]; boolean flipped = false; if (bestXPos == n-1) { --n; } else if (bestXPos == 0) { flip(n-1); --n; } else if (altXPos == n-1) { dir = 1-dir; --n; flipped = true; } else { flip(bestXPos); } sort(n, dir);
if (flipped) { flip(n); } } PancakeSort(int[] numbers) { heap = numbers; sort(numbers.length, 1); } public static void main(String[] args) { int[] numbers = new int[args.length]; for (int i = 0; i < args.length; ++i) numbers[i] = Integer.valueOf(args[i]);
PancakeSort pancakes = new PancakeSort(numbers); System.out.println(pancakes); }
}</lang>
Example: <lang bash>$ java PancakeSort 1 2 5 4 3 10 9 8 7 flip(0..5): 10 3 4 5 2 1 9 8 7 flip(0..8): 7 8 9 1 2 5 4 3 10 flip(0..2): 9 8 7 1 2 5 4 3 10 flip(0..7): 3 4 5 2 1 7 8 9 10 flip(0..2): 5 4 3 2 1 7 8 9 10 flip(0..4): 1 2 3 4 5 7 8 9 10 1 2 3 4 5 7 8 9 10
$ java PancakeSort 6 7 2 1 8 9 5 3 4 flip(0..5): 9 8 1 2 7 6 5 3 4 flip(0..8): 4 3 5 6 7 2 1 8 9 flip(0..1): 3 4 5 6 7 2 1 8 9 flip(0..4): 7 6 5 4 3 2 1 8 9 flip(0..6): 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 </lang>
JavaScript
<lang javascript>Array.prototype.pancake_sort = function () {
for (var i = this.length - 1; i >= 1; i--) { // find the index of the largest element not yet sorted var max_idx = 0; var max = this[0]; for (var j = 1; j <= i; j++) { if (this[j] > max) { max = this[j]; max_idx = j; } }
if (max_idx == i) continue; // element already in place
var new_slice;
// flip this max element to index 0 if (max_idx > 0) { new_slice = this.slice(0, max_idx+1).reverse(); for (var j = 0; j <= max_idx; j++) this[j] = new_slice[j]; }
// then flip the max element to its place new_slice = this.slice(0, i+1).reverse(); for (var j = 0; j <= i; j++) this[j] = new_slice[j]; } return this;
} ary = [7,6,5,9,8,4,3,1,2,0] sorted = ary.concat().pancake_sort();</lang>
Mathematica
<lang Mathematica>LMaxPosition[ a_, n_ ] := Part[Position[a;;n,Max[a;;n]],1,1]
SetAttributes[Flip,HoldFirst]; Flip[a_] := Set[a,Reverse[a]]
pancakeSort[a_] : = For[n = Length[a], n > 1, n--,
If[LMaxPosition[a,n] < n, Flip[a[[;;LMaxPosition[a,n]]]]; Print[a]; Flip[a;;n]; Print[a]; ];
];</lang>
(* each major sort step is printed in example usage *) pancakeSort[{6, 7, 8, 9, 2, 5, 3, 4, 1}] {9,8,7,6,2,5,3,4,1} {1,4,3,5,2,6,7,8,9} {5,3,4,1,2,6,7,8,9} {2,1,4,3,5,6,7,8,9} {4,1,2,3,5,6,7,8,9} {3,2,1,4,5,6,7,8,9} {3,2,1,4,5,6,7,8,9} {1,2,3,4,5,6,7,8,9}
MATLAB / Octave
<lang MATLAB>function list = pancakeSort(list)
for i = (numel(list):-1:2) minElem = list(i); minIndex = i; %Find the min element in the current subset of the list for j = (i:-1:1) if list(j) <= minElem minElem = list(j); minIndex = j; end end %If the element is already in the correct position don't flip if i ~= minIndex
%First flip flips the min element in the stack to the top list(minIndex:-1:1) = list(1:minIndex); %Second flip flips the min element into the correct position in %the stack list(i:-1:1) = list(1:i); end end %for
end %pancakeSort</lang>
Sample Usage: <lang MATLAB>>> pancakeSort([4 3 1 5 6 2])
ans =
6 5 4 3 2 1</lang>
NetRexx
Sorts integers, decimal numbers and strings because they're all the same to NetRexx. <lang NetRexx>/* NetRexx */ options replace format comments java crossref symbols nobinary
import java.util.List
runSample(arg) return
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ method pancakeSort(tlist = List, debug = (1 == 0)) private static returns List
if tlist.size() > 1 then do loop i_ = tlist.size() by -1 while i_ > 1 maxPos = 0 loop a_ = 0 while a_ < i_ if Rexx tlist.get(a_) > Rexx tlist.get(maxPos) then maxPos = a_ end a_ if maxPos = i_ - 1 then iterate i_ if maxPos > 0 then pancakeFlip(tlist, maxPos + 1, debug) pancakeFlip(tlist, i_, debug) end i_ end return tlist
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ method pancakeFlip(tlist = List, offset, debug = (1 == 0)) private static returns List
z_ = offset - 1 pl = 3 if debug then do plx = offset.length() if plx > pl then pl = plx say ' flip{1-'offset.right(pl, 0)'} Before:' tlist end loop i_ = 0 while i_ < z_ Collections.swap(tlist, i_, z_) z_ = z_ - 1 end i_ if debug then do say ' flip{1-'offset.right(pl, 0)'} After:' tlist end return tlist
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ method runSample(arg) private static
isTrue = (1 == 1) isFalse = \isTrue parse arg debug . if '-debug'.abbrev(debug.lower(), 2) then debug = isTrue else debug = isFalse
lists = sampleData() loop il = 1 to lists[0] clist = words2list(lists[il]) say ' Input:' clist say 'Output:' pancakeSort(clist, debug) say end il
return
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ method sampleData() private static
lists = i_ = 0 i_ = i_ + 1; lists[0] = i_; lists[i_] = '1 4 3 5 2 9 8 7 6' i_ = i_ + 1; lists[0] = i_; lists[i_] = '10 -9 8 -7 6 -5 4 -3 2 -1 0 -10 9 -8 7 -6 5 -4 3 -2 1' i_ = i_ + 1; lists[0] = i_; lists[i_] = '88 18 31 44 4 0 8 81 14 78 20 76 84 33 73 75 82 5 62 70 12 7 1' i_ = i_ + 1; lists[0] = i_; lists[i_] = '10 10.0 10.00 1 -10.0 10. -1' i_ = i_ + 1; lists[0] = i_; lists[i_] = 'To be or not to be that is the question' i_ = i_ + 1; lists[0] = i_; lists[i_] = '1' return lists
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ method words2list(wordlist) private static returns List
clist = ArrayList() loop w_ = 1 to wordlist.words() clist.add(wordlist.word(w_)) end w_
return clist
</lang>
- Output:
Input: [1, 4, 3, 5, 2, 9, 8, 7, 6] Output: [1, 2, 3, 4, 5, 6, 7, 8, 9] Input: [10, -9, 8, -7, 6, -5, 4, -3, 2, -1, 0, -10, 9, -8, 7, -6, 5, -4, 3, -2, 1] Output: [-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Input: [88, 18, 31, 44, 4, 0, 8, 81, 14, 78, 20, 76, 84, 33, 73, 75, 82, 5, 62, 70, 12, 7, 1] Output: [0, 1, 4, 5, 7, 8, 12, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88] Input: [10, 10.0, 10.00, 1, -10.0, 10., -1] Output: [-10.0, -1, 1, 10.00, 10.0, 10., 10] Input: [To, be, or, not, to, be, that, is, the, question] Output: [be, be, is, not, or, question, that, the, to, To] Input: [1] Output: [1]
OCaml
<lang ocaml>let rec sorted = function
| [] -> (true) | x::y::_ when x > y -> (false) | x::xs -> sorted xs
let rev_until_max li =
let rec aux acc greater prefix suffix = function | x::xs when x > greater -> aux (x::acc) x acc xs xs | x::xs -> aux (x::acc) greater prefix suffix xs | [] -> (greater, (prefix @ suffix)) in aux [] min_int [] li li
let pancake_sort li =
let rec aux i li suffix = let greater, li = rev_until_max li in let suffix = greater :: suffix and li = List.rev li in if sorted li then (li @ suffix), i else aux (succ i) li suffix in aux 0 li []
let print_list li =
List.iter (Printf.printf " %d") li; print_newline()
let make_rand_list n bound =
let rec aux acc i = if i >= n then (acc) else aux ((Random.int bound)::acc) (succ i) in aux [] 0
let () =
Random.self_init(); let li = make_rand_list 8 100 in print_list li; let res, n = pancake_sort li in print_list res; Printf.printf " sorted in %d loops\n" n;
- </lang>
PARI/GP
<lang parigp>pancakeSort(v)={
my(top=#v); while(top>1, my(mx=1,t); for(i=2,top,if(v[i]>v[mx], mx=i)); if(mx==top, top--; next); for(i=1,mx\2, t=v[i]; v[i]=v[mx+1-i]; v[mx+1-i]=t ); for(i=1,top\2, t=v[i]; v[i]=v[top+1-i]; v[top+1-i]=t ); top-- ); v
};</lang>
Pascal
<lang pascal>Program PancakeSort (output);
procedure flip(var b: array of integer; last: integer);
var swap, i: integer;
begin for i := low(b) to (last - low(b) - 1) div 2 do begin swap := b[i]; b[i] := b[last-(i-low(b))]; b[last-(i-low(b))] := swap; end; end;
procedure PancakeSort(var a: array of integer);
var i, j, maxpos: integer;
begin for i := high(a) downto low(a) do begin
// Find position of max number between beginning and i
maxpos := i; for j := low(a) to i - 1 do if a[j] > a[maxpos] then maxpos := j;
// is it in the correct position already?
if maxpos = i then continue;
// is it at the beginning of the array? If not flip array section so it is
if maxpos <> low(a) then flip(a, maxpos);
// Flip array section to get max number to correct position
flip(a, i); end; end;
var
data: array of integer; i: integer;
begin
setlength(data, 8); Randomize; writeln('The data before sorting:'); for i := low(data) to high(data) do begin data[i] := Random(high(data)); write(data[i]:4); end; writeln; PancakeSort(data); writeln('The data after sorting:'); for i := low(data) to high(data) do begin write(data[i]:4); end; writeln;
end.</lang> Output:
:>./PancakeSort The data before sorting: 3 1 3 2 4 0 2 6 The data after sorting: 0 1 2 2 3 3 4 6
Perl
<lang perl>sub pancake {
my @x = @_; for my $idx (0 .. $#x - 1) { my $min = $idx; $x[$min] > $x[$_] and $min = $_ for $idx + 1 .. $#x;
next if $x[$min] == $x[$idx];
@x[$min .. $#x] = reverse @x[$min .. $#x] if $x[$min] != $x[-1]; @x[$idx .. $#x] = reverse @x[$idx .. $#x]; } @x;
}
my @a = map (int rand(100), 1 .. 10); print "Before @a\n"; @a = pancake(@a); print "After @a\n"; </lang> Sample output:
Before 57 37 35 35 22 58 70 53 77 15 After 15 22 35 35 37 53 57 58 70 77
Perl 6
<lang perl6>sub pancake_sort ( @a is copy ) {
my $endpoint = @a.end; while $endpoint > 0 and not [<] @a { my $max_i = [0..$endpoint].max: { @a[$_] }; my $max = @a[$max_i]; if @a[$endpoint] == $max { $endpoint-- while @a[$endpoint] == $max; next; } # @a[$endpoint] is not $max, so it needs flipping; # Flip twice if max is not already at the top. @a[0..$max_i] .= reverse if $max_i != 0; @a[0..$endpoint] .= reverse; $endpoint--; } return @a;
} my @data = 6, 7, 2, 1, 8, 9, 5, 3, 4; say 'input = ' ~ @data; say 'output = ' ~ @data.&pancake_sort; </lang>
Output:
input = 6 7 2 1 8 9 5 3 4 output = 1 2 3 4 5 6 7 8 9
PL/I
<lang PL/I> pancake_sort: procedure options (main); /* 23 April 2009 */
declare a(10) fixed, (i, n, loc) fixed binary;
a(1) = 3; a(2) = 9; a(3) = 2; a(4) = 7; a(5) = 10; a(6) = 1; a(7) = 8; a(8) = 5; a(9) = 4; a(10) = 6;
n = hbound(A,1); put skip edit (A) (f(5)); do i = 1 to n-1; loc = max(A, n); call flip (A, loc); call flip (A, n); n = n - 1; put skip edit (A) (f(5)); end;
max: procedure (A, k) returns (fixed binary);
declare A(*) fixed, k fixed binary; declare (i, maximum, loc) fixed binary; maximum = A(1); loc = 1; do i = 2 to k; if A(i) > maximum then do; maximum = A(i); loc = i; end; end; return (loc);
end max;
flip: procedure (A, k);
declare A(*) fixed, k fixed binary; declare (i, t) fixed binary; do i = 1 to (k+1)/2; t = A(i); A(i) = A(k-i+1); A(k-i+1) = t; end;
end flip;
end pancake_sort; </lang> Output: <lang>
3 9 2 7 10 1 8 5 4 6 6 4 5 8 1 3 9 2 7 10 7 2 6 4 5 8 1 3 9 10 3 1 7 2 6 4 5 8 9 10 5 4 6 2 3 1 7 8 9 10 1 3 2 5 4 6 7 8 9 10 4 1 3 2 5 6 7 8 9 10 2 3 1 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
</lang>
PicoLisp
<lang PicoLisp>(de pancake (Lst)
(prog1 (flip Lst (index (apply max Lst) Lst)) (for (L @ (cdr (setq Lst (cdr L))) (cdr L)) (con L (flip Lst (index (apply max Lst) Lst))) ) ) )</lang>
Output:
: (trace 'flip) -> flip : (pancake (6 7 2 1 8 9 5 3 4)) flip : (6 7 2 1 8 9 5 3 4) 6 flip = (9 8 1 2 7 6 5 3 4) flip : (8 1 2 7 6 5 3 4) 1 flip = (8 1 2 7 6 5 3 4) flip : (1 2 7 6 5 3 4) 3 flip = (7 2 1 6 5 3 4) flip : (2 1 6 5 3 4) 3 flip = (6 1 2 5 3 4) flip : (1 2 5 3 4) 3 flip = (5 2 1 3 4) flip : (2 1 3 4) 4 flip = (4 3 1 2) flip : (3 1 2) 1 flip = (3 1 2) flip : (1 2) 2 flip = (2 1) -> (9 8 7 6 5 4 3 2 1)
PowerShell
<lang PowerShell>Function FlipPancake( [Object[]] $indata, $index = 1 ) { $data=$indata.Clone() $datal = $data.length - 1 if( $index -gt 0 ) { if( $datal -gt $index ) { $first = $data[ $index..0 ] $last = $data[ ( $index + 1 )..$datal ] $data = $first + $last } else { $data = $data[ $index..0 ] } } $data }
Function MaxIdx( [Object[]] $data ) { $data | ForEach-Object { $max = $data[ 0 ]; $i = 0; $maxi = 0 } { if( $_ -gt $max ) { $max = $_; $maxi = $i }; $i++ } { $maxi } }
Function PancakeSort( [Object[]] $data, $index = 0 ) { "unsorted - $data" $datal = $data.length - 1 if( $datal -gt 0 ) { for( $i = $datal; $i -gt 0; $i-- ) { $data = FlipPancake ( FlipPancake $data ( MaxIdx $data[ 0..$i ] ) ) $i } } "sorted - $data" }
$l = 100; PancakeSort ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( 0, $l - 1 ) } )</lang>
PureBasic
<lang PureBasic>If OpenConsole()
Define i, j, k, Loops Dim Pile(9) ;-------------------------------------------------------------- ;- Create a Random Pile() For i=1 To 9 ;- Initiate the Pile Pile(i)=i Next For i=9 To 1 Step -1 ;- Do a Fisher-Yates shuffle Swap Pile(i),Pile(Random(i-1)+1) Next Print("Random Pile() :") For i=1 To 9 Print(" "+Str(Pile(i))) Next ;-------------------------------------------------------------- ;- Start Sorting For i=9 To 2 Step -1 If Pile(i)<>i ;- Only Flip it if the current cake need Swapping Loops+1 j=0 Repeat ;- find place of Pancake(i) in the Pile() j+1 Until Pile(j)=i For k=1 To (j/2) ;- Flip it up Swap Pile(k),Pile(j-k+1) Next For k=1 To i/2 ;- Flip in place Swap Pile(k),Pile(i-k+1) Next EndIf Next Print(#CRLF$+"Resulting Pile() :") For i=1 To 9 Print(" "+str(Pile(i))) Next Print(#CRLF$+"All done in "+str(Loops)+" loops.") Print(#CRLF$+#CRLF$+"Press ENTER to quit."): Input() CloseConsole()
EndIf</lang>
Output can look like
Original Pile() : 9 4 1 8 6 3 2 5 7 Resulting Pile() : 1 2 3 4 5 6 7 8 9 All done in 6 loops. Press ENTER to quit.
Python
The function: <lang python>tutor = False
def pancakesort(data):
if len(data) <= 1: return data if tutor: print() for size in range(len(data), 1, -1): maxindex = max(range(size), key=data.__getitem__) if maxindex+1 != size: # This indexed max needs moving if maxindex != 0: # Flip the max item to the left if tutor: print('With: %r doflip %i' % ( ' '.join(str(x) for x in data), maxindex+1 )) data[:maxindex+1] = reversed(data[:maxindex+1]) # Flip it into its final position if tutor: print('With: %r doflip %i' % ( ' '.join(str(x) for x in data), size )) data[:size] = reversed(data[:size]) if tutor: print()</lang>
A test: <lang python>if __name__ == '__main__':
import random
tutor = True data = list('123456789') while data == sorted(data): random.shuffle(data) print('Original List: %r' % ' '.join(data)) pancakesort(data) print('Pancake Sorted List: %r' % ' '.join(data))</lang>
Sample output:
Original List: '6 7 2 1 8 9 5 3 4' With: '6 7 2 1 8 9 5 3 4' doflip 6 With: '9 8 1 2 7 6 5 3 4' doflip 9 With: '4 3 5 6 7 2 1 8 9' doflip 5 With: '7 6 5 3 4 2 1 8 9' doflip 7 With: '1 2 4 3 5 6 7 8 9' doflip 3 With: '4 2 1 3 5 6 7 8 9' doflip 4 With: '3 1 2 4 5 6 7 8 9' doflip 3 With: '2 1 3 4 5 6 7 8 9' doflip 2 Pancake Sorted List: '1 2 3 4 5 6 7 8 9'
REXX
<lang rexx>/*REXX program sorts/shows an array using the pancake sort algorithm.*/ call gen@ /*generate elements in the array.*/ call show@ 'before sort' /*show the BEFORE array elements.*/ call pancakeSort #items /*invoke the pancake sort. Yummy.*/ call show@ ' after sort' /*show the AFTER array elements.*/ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────PANCAKESORT subroutine──────────────*/ pancakeSort: procedure expose @.; parse arg n
do n-1 /*perform this loop N-1 times.*/ !=@.1; ?=1 do j=2 to n if @.j<=! then iterate !=@.j; ?=j end /*j*/ call flip ?; call flip n n=n-1 end /*n-1*/
return /*──────────────────────────────────FLIP subroutine─────────────────────*/ flip: procedure expose @.; parse arg w
do i=1 for (w+1)%2 /*In REXX, % is integer divide.*/ kmip1=w-i+1; _=@.i; @.i=@.kmip1; @.kmip1=_ end /*i*/
return /*──────────────────────────────────GEN@ subroutine─────────────────────*/ gen@: @.= /*assign a default value. */
/*Generate some bread primes which are primes of the*/ /*form: (p-3)÷2 and 2∙p+3 where p is a prime.*/ /*Bread primes are related to sandwich & meat primes.*/
@.1= 2 ; @.17= 113 ; @.33= -55 @.2= 17 ; @.18= 461 ; @.34= -21 @.3= 5 ; @.19= 137 ; @.35= -1 @.4= 29 ; @.20= 557 ; @.36= -8 @.5= 7 ; @.21= 167 ; @.37= -8 @.6= 37 ; @.22= 677 ; @.38= -21 @.7= 13 ; @.23= 173 ; @.39= -55 @.8= 61 ; @.24= 701 ; @.40= 0 @.9= 43 ; @.25= 797 ; @.41= 0
@.10= 181 ; @.26= 1117 @.11= 47 ; @.27= 307 /*The non-positive numbers*/ @.12= 197 ; @.28= 1237 /*above are some negative */ @.13= 67 ; @.29= 1597 /*Fibonacci numbers, some */ @.14= 277 ; @.30= 463 /*of which where specified*/ @.15= 97 ; @.31= 1861 /*twice just 'cause I felt*/ @.16= 397 ; @.32= 467 /*like it. Also, added */
/*two zeroes, just 'cause.*/ do #items=1 while @.#items\==; end /*find how many entries in array.*/
- items=#items-1 /*adjust the #items slightly. */
return /*──────────────────────────────────SHOW@ subroutine────────────────────*/ show@: widthH=length(#items) /*the maximum width of any line. */
do k=1 for #items say 'element' right(k,widthH) arg(1)':' @.k end /*k*/
say copies('─',79) /*show an eyeball separator line.*/ return</lang> output
element 1 before sort: 2 element 2 before sort: 17 element 3 before sort: 5 element 4 before sort: 29 element 5 before sort: 7 element 6 before sort: 37 element 7 before sort: 13 element 8 before sort: 61 element 9 before sort: 43 element 10 before sort: 181 element 11 before sort: 47 element 12 before sort: 197 element 13 before sort: 67 element 14 before sort: 277 element 15 before sort: 97 element 16 before sort: 397 element 17 before sort: 113 element 18 before sort: 461 element 19 before sort: 137 element 20 before sort: 557 element 21 before sort: 167 element 22 before sort: 677 element 23 before sort: 173 element 24 before sort: 701 element 25 before sort: 797 element 26 before sort: 1117 element 27 before sort: 307 element 28 before sort: 1237 element 29 before sort: 1597 element 30 before sort: 463 element 31 before sort: 1861 element 32 before sort: 467 element 33 before sort: -55 element 34 before sort: -21 element 35 before sort: -1 element 36 before sort: -8 element 37 before sort: -8 element 38 before sort: -21 element 39 before sort: -55 element 40 before sort: 0 element 41 before sort: 0 ─────────────────────────────────────────────────────────────────────────────── element 1 after sort: -55 element 2 after sort: -55 element 3 after sort: -21 element 4 after sort: -21 element 5 after sort: -8 element 6 after sort: -8 element 7 after sort: -1 element 8 after sort: 0 element 9 after sort: 0 element 10 after sort: 2 element 11 after sort: 5 element 12 after sort: 7 element 13 after sort: 13 element 14 after sort: 17 element 15 after sort: 29 element 16 after sort: 37 element 17 after sort: 43 element 18 after sort: 47 element 19 after sort: 61 element 20 after sort: 67 element 21 after sort: 97 element 22 after sort: 113 element 23 after sort: 137 element 24 after sort: 167 element 25 after sort: 173 element 26 after sort: 181 element 27 after sort: 197 element 28 after sort: 277 element 29 after sort: 307 element 30 after sort: 397 element 31 after sort: 461 element 32 after sort: 463 element 33 after sort: 467 element 34 after sort: 557 element 35 after sort: 677 element 36 after sort: 701 element 37 after sort: 797 element 38 after sort: 1117 element 39 after sort: 1237 element 40 after sort: 1597 element 41 after sort: 1861 ───────────────────────────────────────────────────────────────────────────────
Ruby
<lang ruby>class Array
def pancake_sort! num_flips = 0 (self.size-1).downto(1) do |end_idx| max = self[0..end_idx].max max_idx = self[0..end_idx].index(max) next if max_idx == end_idx if max_idx > 0 self[0..max_idx] = self[0..max_idx].reverse p [num_flips += 1, self] if $DEBUG end self[0..end_idx] = self[0..end_idx].reverse p [num_flips += 1, self] if $DEBUG end self end
end
p a = (1..9).to_a.shuffle p a.pancake_sort!</lang>
sample output:
$ ruby -d sorting_pancake.rb [7, 3, 6, 8, 2, 4, 5, 1, 9] [1, [8, 6, 3, 7, 2, 4, 5, 1, 9]] [2, [1, 5, 4, 2, 7, 3, 6, 8, 9]] [3, [7, 2, 4, 5, 1, 3, 6, 8, 9]] [4, [6, 3, 1, 5, 4, 2, 7, 8, 9]] [5, [2, 4, 5, 1, 3, 6, 7, 8, 9]] [6, [5, 4, 2, 1, 3, 6, 7, 8, 9]] [7, [3, 1, 2, 4, 5, 6, 7, 8, 9]] [8, [2, 1, 3, 4, 5, 6, 7, 8, 9]] [9, [1, 2, 3, 4, 5, 6, 7, 8, 9]] [1, 2, 3, 4, 5, 6, 7, 8, 9]
Tcl
<lang tcl>package require Tcl 8.5
- Some simple helper procedures
proc flip {nlist n} {
concat [lreverse [lrange $nlist 0 $n]] [lrange $nlist $n+1 end]
} proc findmax {nlist limit} {
lsearch -exact $nlist [tcl::mathfunc::max {*}[lrange $nlist 0 $limit]]
}
- Simple-minded pancake sort algorithm
proc pancakeSort {nlist {debug ""}} {
for {set i [llength $nlist]} {[incr i -1] > 0} {} {
set j [findmax $nlist $i] if {$i != $j} { if {$j} { set nlist [flip $nlist $j] if {$debug eq "debug"} {puts [incr flips]>>$nlist} } set nlist [flip $nlist $i] if {$debug eq "debug"} {puts [incr flips]>>$nlist} }
} return $nlist
}</lang> Demonstrate (with debug mode enabled so it prints intermediate states): <lang tcl>puts [pancakeSort {27916 5928 23535 14711 32184 14621 21093 14422 29844 11093} debug]</lang> Output:
1>>32184 14711 23535 5928 27916 14621 21093 14422 29844 11093 2>>11093 29844 14422 21093 14621 27916 5928 23535 14711 32184 3>>29844 11093 14422 21093 14621 27916 5928 23535 14711 32184 4>>14711 23535 5928 27916 14621 21093 14422 11093 29844 32184 5>>27916 5928 23535 14711 14621 21093 14422 11093 29844 32184 6>>11093 14422 21093 14621 14711 23535 5928 27916 29844 32184 7>>23535 14711 14621 21093 14422 11093 5928 27916 29844 32184 8>>5928 11093 14422 21093 14621 14711 23535 27916 29844 32184 9>>21093 14422 11093 5928 14621 14711 23535 27916 29844 32184 10>>14711 14621 5928 11093 14422 21093 23535 27916 29844 32184 11>>14422 11093 5928 14621 14711 21093 23535 27916 29844 32184 12>>5928 11093 14422 14621 14711 21093 23535 27916 29844 32184 5928 11093 14422 14621 14711 21093 23535 27916 29844 32184
As you can see, it took 12 flips.
VBA
<lang vb>
'pancake sort 'uses two auxiliary routines "printarray" and "flip"
Public Sub printarray(A)
For i = LBound(A) To UBound(A) Debug.Print A(i), Next Debug.Print
End Sub
Public Sub Flip(ByRef A, p1, p2, trace) 'flip first elements of A (p1 to p2)
If trace Then Debug.Print "we'll flip the first "; p2 - p1 + 1; "elements of the array" Cut = Int((p2 - p1 + 1) / 2) For i = 0 To Cut - 1 'flip position i and (n - i + 1) temp = A(i) A(i) = A(p2 - i) A(p2 - i) = temp Next
End Sub
Public Sub pancakesort(ByRef A(), Optional trace As Boolean = False) 'sort A into ascending order using pancake sort
lb = LBound(A) ub = UBound(A) Length = ub - lb + 1 If Length <= 1 Then 'no need to sort
Exit Sub
End If
For i = ub To lb + 1 Step -1
'find position of max. element in subarray A(lowerbound to i) P = lb Maximum = A(P) For j = lb + 1 To i If A(j) > Maximum Then P = j Maximum = A(j) End If Next j 'check if maximum is already at end - then we don't need to flip If P < i Then 'flip the first part of the array up to the maximum so it is at the head - skip if it is already there If P > 1 Then Flip A, lb, P, trace If trace Then printarray A End If 'now flip again so that it is in its final position Flip A, lb, i, trace If trace Then printarray A End If
Next i End Sub
'test routine Public Sub TestPancake(Optional trace As Boolean = False) Dim A() A = Array(5, 7, 8, 3, 1, 10, 9, 23, 50, 0) Debug.Print "Initial array:" printarray A pancakesort A, trace Debug.Print "Final array:" printarray A End Sub </lang>
Sample output:
testpancake True Initial array: 5 7 8 3 1 10 9 23 50 0 we'll flip the first 9 elements of the array 50 23 9 10 1 3 8 7 5 0 we'll flip the first 10 elements of the array 0 5 7 8 3 1 10 9 23 50 we'll flip the first 7 elements of the array 10 1 3 8 7 5 0 9 23 50 we'll flip the first 8 elements of the array 9 0 5 7 8 3 1 10 23 50 we'll flip the first 7 elements of the array 1 3 8 7 5 0 9 10 23 50 we'll flip the first 3 elements of the array 8 3 1 7 5 0 9 10 23 50 we'll flip the first 6 elements of the array 0 5 7 1 3 8 9 10 23 50 we'll flip the first 3 elements of the array 7 5 0 1 3 8 9 10 23 50 we'll flip the first 5 elements of the array 3 1 0 5 7 8 9 10 23 50 we'll flip the first 3 elements of the array 0 1 3 5 7 8 9 10 23 50 Final array: 0 1 3 5 7 8 9 10 23 50