
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


Task

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).



Related tasks

   Number reversal game
   Topswops


Also see

   Wikipedia article:   pancake sorting.


PRINT "Pancake sort:"
  n = FUNC (_InitArray)
  PROC _ShowArray (n)
  PROC _Pancakesort (n)
  PROC _ShowArray (n)
PRINT
 
END
 
 
_Flip PARAM(1)
  LOCAL(1)
 
  b@ = 0
 
  DO WHILE b@ < a@
    PROC _Swap (b@, a@)
    b@ = b@ + 1
    a@ = a@ - 1
  LOOP
RETURN
 
 
_Pancakesort PARAM (1)                 ' Pancakesort
  LOCAL(3)
 
  IF a@ < 2 THEN RETURN
 
  FOR b@ = a@ TO 2 STEP -1
 
    c@  = 0
 
    FOR d@ = 0 TO b@ - 1
      IF @(d@) > @(c@) THEN c@ = d@
    NEXT
 
    IF c@ = b@ - 1 THEN CONTINUE
    IF c@ THEN PROC _Flip (c@)
    PROC _Flip (b@ - 1)
 
  NEXT
RETURN
 
 
_Swap PARAM(2)                         ' Swap two array elements
  PUSH @(a@)
  @(a@) = @(b@)
  @(b@) = POP()
RETURN
 
 
_InitArray                             ' Init example array
  PUSH 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
 
  FOR i = 0 TO 9
    @(i) = POP()
  NEXT
 
RETURN (i)
 
 
_ShowArray PARAM (1)                   ' Show array subroutine
  FOR i = 0 TO a@-1
    PRINT @(i),
  NEXT
 
  PRINT
RETURN