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:
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
<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) = INT(RND * 32768) 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
END IF
FOR L0 = 0 TO (L1 \ 2)
SWAP nums(L0), nums(L1 - L0)
NEXT
END IF
FOR L0 = 0 TO 9
PRINT nums(L0);
NEXT
PRINT
NEXT</lang>
Sample output:
27916 5928 23535 14711 32184 14621 21093 14422 29844 11093 11093 29844 14422 21093 14621 27916 5928 23535 14711 32184 14711 23535 5928 27916 14621 21093 14422 11093 29844 32184 11093 14422 21093 14621 14711 23535 5928 27916 29844 32184 5928 11093 14422 21093 14621 14711 23535 27916 29844 32184 14711 14621 5928 11093 14422 21093 23535 27916 29844 32184 14422 11093 5928 14621 14711 21093 23535 27916 29844 32184 5928 11093 14422 14621 14711 21093 23535 27916 29844 32184
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]