Sorting algorithms/Pancake sort

From Rosetta Code
< Sorting algorithms
Revision as of 15:35, 5 April 2010 by rosettacode>Dkf (whitespace)
Task
Sorting algorithms/Pancake sort
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:

O(n logn) sorts

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.

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: Number reversal game

BASIC

Works with: QBasic
Works with: FreeBASIC

<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

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>

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=0 To 50                            ;- Mix it up
   Swap Pile(Random(8)+1),Pile(Random(8)+1)
 Next
 
 Print("Original 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 = data.index(max(data[:size]))
       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'

Ruby

<lang ruby>class Array 

 def pancake_sort!
   num_flips = 0
   self.size.downto(2) do |i|
     end_idx = i - 1
     max_idx = self[0..end_idx].each_with_index.max_by {|e| e[0]}.last
     next if max_idx == end_idx

     if max_idx > 0
       self[0..max_idx] = self[0..max_idx].reverse 

       if $DEBUG
         num_flips += 1
         p [num_flips, self]
       end
     end

     self[0..end_idx] = self[0..end_idx].reverse 

     if $DEBUG
       num_flips += 1
       p [num_flips, self]
     end
   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

  1. 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]]

}

  1. 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: <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.

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