Sorting algorithms/Pancake sort: Difference between revisions
Line 280: | Line 280: | ||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
<lang C sharp|C#> |
<lang C sharp|C#> |
||
public static class PancakeSorter |
|||
{ |
{ |
||
public static void Sort<T>(List<T> list) where T : IComparable |
public static void Sort<T>(List<T> list) where T : IComparable |
||
Line 319: | Line 320: | ||
list[num] = swap; |
list[num] = swap; |
||
} |
} |
||
} |
|||
} |
} |
||
</lang> |
|||
=={{header|D}}== |
=={{header|D}}== |
Revision as of 09:26, 31 August 2010
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
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:
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>
Testing the function:
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>
D
D v2, from the Python version. <lang d>import std.stdio, std.algorithm, std.range, std.random;
void pancakeSort(bool tutor=false, T)(T[] data) {
if (data.length <= 1) return; foreach_reverse (size; 2 .. data.length + 1) { int maxIndex = size - minPos!("a > b")(data[0 .. size]).length; if (maxIndex + 1 != size) { // This indexed max needs moving if (maxIndex != 0) { // Flip the max item to the left static if (tutor) writeln("With: ", data, " doflip ", maxIndex + 1); data[0 .. maxIndex + 1].reverse; } // Flip it into its final position static if (tutor) writeln("With: ", data, " doflip ", size); data[0 .. size].reverse; } }
}
void main() {
char[] data = "123456789".dup; while (data == data.dup.sort) randomShuffle(data); writeln("Original List: ", data); pancakeSort!true(data); writeln("Pancake Sorted List: ", data);
}</lang> Example output:
Original array: 769248135 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 Pancake sorted array: 123456789
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
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>
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.
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>
MATLAB
<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>
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>
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)
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'
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
- 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.