Sorting algorithms/Pancake sort: Difference between revisions

{{task|Sorting Algorithms}}

{{Sorting Algorithm}}

 

 

In short, instead of individual elements being sorted, the only operation allowed is to "flip" one end of the list, like so:

 

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

 

 

 

<br><br>

 

=={{header|Ada}}==

 

procedure Pancake_Sort is

generic

end loop;

Ada.Text_IO.New_Line;

 

Output:

=={{header|ALGOL 68}}==

{{trans|Euphoria}}

BEGIN

[UPB s]INT ss := s;

printf (($"unsorted: "10(g(4) )l$, s));

printf (($"sorted: "10(g(4) )l$, pancake sort(s)))

{{out}}

<pre>Pancake sort demonstration

sorted: -47 -41 -26 -7 -4 -2 +8 +21 +31 +41

</pre>

=={{header|AutoHotkey}}==

Loop { ; test loop

;---------------------------------------------------------------------------

Return, List

}

 

=={{header|BASIC}}==

{{works with|QBasic}}

 

 

DIM nums(9) AS INTEGER

PRINT

END IF

 

Sample output:

This is a graphical variation of the above.

 

 

CONST delay = .1 'controls display speed

ttmp = TIMER

DO WHILE TIMER < ttmp + delay: LOOP

 

Sample output:

[[File:Pancake.gif]]

 

 

 

=={{header|BBC BASIC}}==

test() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1

PROCpancakesort(test())

SWAP a(i%), a(n%-i%)

NEXT

'''Output:'''

<pre>

=={{header|C}}==

'''The function that sorts:'''

{

//If it's less than 2 long, just return it as sorting isn't really needed...

 

return moves;

 

Where do_flip() is a simple function to flip a part of an array:

{

int swap;

list[num]=swap;

}

 

'''Testing the function:'''

{

//Just need some random numbers. I chose <100

print_array(list, 9);

printf(" - with a total of %d moves\n", moves);

 

=={{header|C++}}==

#include <iostream>

#include <iterator>

std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "));

std::cout << "\n";

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 </pre>

 

=={{header|Clojure}}==

(defn pancake-sort

[arr]

head (reverse torev)]

(cons mx (pancake-sort (concat (drop 1 head) (drop 1 tail))))))))

 

=={{header|Common Lisp}}==

"A destructive version of Pancake Sort that works with either lists or arrays of numbers."

(defun flip (lst index)

(flip lst (1+ index)))

(flip lst i)

Output:

(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

 

=={{header|D}}==

{{trans|Python}}

 

void pancakeSort(bool tutor=false, T)(T[] data) {

data.pancakeSort!true;

data.writeln;

{{out}}

<pre>With: 769248135 doflip 3

 

=={{header|Eiffel}}==

class

PANCAKE_SORT [G -> COMPARABLE]

 

end

 

Test:

class

APPLICATION

 

end

{{out}}

<pre>

Sorted: -7 1 1 3 5 27 32 99

</pre>

=={{header|Elena}}==

{{trans|C#}}

extension op

public program()

{

console.printLine("before:", list.asEnumerable());

console.printLine("after :", list.pancakeSort().asEnumerable())

{{out}}

<pre>

 

=={{header|Elixir}}==

def pancake_sort(list) when is_list(list), do: pancake_sort(list, length(list))

 

IO.inspect list = Enum.shuffle(1..9)

 

{{out}}

 

=={{header|Euphoria}}==

object temp

for i = 1 to n/2 do

 

? s

 

Output:

 

=={{header|F_Sharp|F#}}==

 

let show data = data |> Array.iter (printf "%d ") ; printfn ""

loop partialSort (limit-1)

 

Usage: pancakeSort [|31; 41; 59; 26; 53; 58; 97; 93; 23; 84|] |> show

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

implicit none

end subroutine

Output:

<pre>

1 2 3 4 5 6 7 8

</pre>

=={{header|FreeBASIC}}==

' compile with: fbc -s console

' for boundry checks on array's compile with: fbc -s console -exx

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>unsorted -1 -4 1 6 7 5 2 -3 4 -5 -2 -6 0 3 -7

 

=={{header|Go}}==

 

import "fmt"

a[l], a[r] = a[r], a[l]

}

Output:

<pre>

=={{header|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.

 

def flip = { list, n -> (0..<((n+1)/2)).each { makeSwap(list, it, n-it) } }

}

list

 

Test:

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.0, 10.00, 10, 1]))

println (pancakeSort([10.00, 10, 10.0, 1]))

The use of decimals and integers that compare as equal demonstrates, but of course not '''prove''', that the sort is stable.

 

 

=={{header|Haskell}}==

import Control.Arrow

import Control.Monad

dopcs ([],rs) = rs

dopcs ([x],rs) = x:rs

Example:

 

=={{header|Icon}} and {{header|Unicon}}==

demosort(pancakesort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")

pancakeflip := pancakeflipshow # replace pancakeflip procedure with a variant that displays each flip

every writes(" ["|right(!X,4)|" ]\n") # show X

return X

 

Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| 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.

=={{header|J}}==

{{eff note|J|/:~}}

unsorted=: #~ 1 , [: >./\. 2 >/\ ]

FlDown=: flip 1 + (i. >./)@unsorted

FlipUp=: flip 1 >. [:+/>./\&|.@(< {.)

 

 

Example use:

 

1 0 8 7 4 6 3 5 2

 

See the [[Talk:Sorting_algorithms/Pancake_sort#J_implementation|discussion page]] for illustrations of the other words.

=={{header|Java}}==

 

public class PancakeSort

{

System.out.println(pancakes);

}

 

Example:

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..4): 7 6 5 4 3 2 1 8 9

flip(0..6): 1 2 3 4 5 6 7 8 9

 

=={{header|JavaScript}}==

for (var i = this.length - 1; i >= 1; i--) {

// find the index of the largest element not yet sorted

}

ary = [7,6,5,9,8,4,3,1,2,0]

 

=={{header|jq}}==

{{works with|jq|1.4}}

This version skips the pair of flips if the focal item is already in place.

 

def flip(i):

| if ($i == $max) then .

else flip($max) | flip($i)

'''Example''':

 

{{out}}

 

=={{header|Julia}}==

len = length(arr)

if len < 2 return arr end

for i in len:-1:2

if i == j continue end

arr[1:j] = reverse(arr[1:j])

 

v = rand(-10:10, 10)

 

{{out}}

 

=={{header|Kotlin}}==

 

}

}

}

}

val a = intArrayOf(7, 6, 9, 2, 4, 8, 1, 3, 5)

println("${a.contentToString()} initially")

 

{{out}}

 

=={{header|Lua}}==

math.randomseed(os.time())

numList = {step = 0, sorted = 0}

numList:show()

until numList:isSorted()

{{out}}

<pre>Initial state: -67 61 80 47 21 74 43 22 66 -66

 

=={{header|Maple}}==

local start, temp, icopy;

temp, start, icopy := 0,1,i:

end do:

print(arr);

{{Out|Example}}

Input: arr := Array([17,3,72,0,36,2,3,8,40,1]):

[0, 1, 2, 3, 3, 8, 17, 36, 40, 72]</pre>

 

{1,4,3,5,2,6,7,8,9}

{5,3,4,1,2,6,7,8,9}

 

=={{header|MATLAB}} / {{header|Octave}}==

 

for i = (numel(list):-1:2)

end

end %for

 

Sample Usage:

 

ans =

 

 

=={{header|MAXScript}}==

(

local new = #()

return arr

)

Output:

a = for i in 1 to 15 collect random 0 20

#(8, 13, 2, 0, 10, 8, 1, 15, 4, 7, 6, 9, 11, 3, 5)

pancakeSort a

#(0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 10, 11, 13, 15)

 

=={{header|NetRexx}}==

Sorts integers, decimal numbers and strings because they're all the same to NetRexx.

options replace format comments java crossref symbols nobinary

 

 

return clist

{{out}}

<pre>

 

=={{header|Nim}}==

 

proc pancakeSort[T](list: var openarray[T]) =

for i in countdown(length, 2):

var maxNumPos = 0

if list[a] > list[maxNumPos]:

maxNumPos = a

var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]

pancakeSort a

Output:

<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>

 

=={{header|OCaml}}==

| [] -> (true)

| x::y::_ when x > y -> (false)

print_list res;

Printf.printf " sorted in %d loops\n" n;

 

=={{header|PARI/GP}}==

my(top=#v);

while(top>1,

);

v

 

=={{header|Pascal}}==

 

procedure flip(var b: array of integer; last: integer);

end;

writeln;

Output:

<pre>:>./PancakeSort

 

=={{header|Perl}}==

my @x = @_;

for my $idx (0 .. $#x - 1) {

@a = pancake(@a);

print "After @a\n";

Sample output:

<pre>Before 57 37 35 35 22 58 70 53 77 15

After 15 22 35 35 37 53 57 58 70 77</pre>

 

=={{header|Phix}}==

{{out}}

<pre>

{1,2,3,4,5,6,7,8,9,10}

</pre>

 

=={{header|PicoLisp}}==

(prog1 (flip Lst (index (apply max Lst) Lst))

(for (L @ (cdr (setq Lst (cdr L))) (cdr L))

Output:

<pre>: (trace 'flip)

 

=={{header|PL/I}}==

pancake_sort: procedure options (main); /* 23 April 2009 */

declare a(10) fixed, (i, n, loc) fixed binary;

 

end pancake_sort;

Output:

3 9 2 7 10 1 8 5 4 6

6 4 5 8 1 3 9 2 7 10

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

 

=={{header|PowerShell}}==

{

$data=$indata.Clone()

}

 

 

=={{header|PureBasic}}==

 

Define i, j, k, Loops

Dim Pile(9)

Print(#CRLF$+#CRLF$+"Press ENTER to quit."): Input()

CloseConsole()

 

'''Output can look like

=={{header|Python}}==

'''The function:'''

 

def pancakesort(data):

% ( ' '.join(str(x) for x in data), size ))

data[:size] = reversed(data[:size])

'''A test:'''

import random

 

print('Original List: %r' % ' '.join(data))

pancakesort(data)

 

'''Sample output:'''

 

Pancake Sorted List: '1 2 3 4 5 6 7 8 9'</pre>

 

=={{header|Racket}}==

#lang racket

 

(pancake-sort (shuffle (range 0 10)))

;; => '(0 1 2 3 4 5 6 7 8 9)

 

=={{header|REXX}}==

call gen /*generate elements in the @. array.*/

call show 'before sort' /*display the BEFORE array elements.*/

call pancakeSort # /*invoke the pancake sort. Yummy. */

call show ' after sort' /*display the AFTER array elements. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

show: do k=1 for #; say @element right(k,length(#)) arg(1)':' right(@.k,9); end; return

/*──────────────────────────────────────────────────────────────────────────────────────*/

/* ┌◄─┬──◄─ some paired bread primes which are of the form: (P-3)÷2 and 2∙P+3 */

/* │ │ where P is a prime. Bread primes are related to sandwich & meat primes*/

bp=2 17 5 29 7 37 13 61 43 181 47 197 67 277 97 397 113 461 137 557 167 677 173 701,

797 1117 307 1237 1597 463 1861 467

return /* [↑] populate the @. array with #s*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the internally generated numbers:}}

 

<small>(Shown at three-quarter size.)</small>

element 1 before sort: 2

element 2 before sort: 17

 

=={{header|Ring}}==

pancakeList = [6, 7, 8, 9, 2, 5, 3, 4, 1]

flag = 0

end

return A

Output:

<pre>

 

=={{header|Ruby}}==

def pancake_sort!

num_flips = 0

 

p a = (1..9).to_a.shuffle

 

'''sample output:'''

 

=={{header|Rust}}==

let len = v.len();

// trivial case -- no flips

pancake_sort(&mut strings);

println!("After: {:?}", strings);

 

=={{header|Sidef}}==

{{trans|Perl}}

for idx in ^(a.end) {

var min = idx

var arr = 10.of{ 100.irand }

say "Before: #{arr}"

 

{{out}}

=={{header|Swift}}==

{{trans|Java}}

 

struct PancakeSort {

var a = PancakeSort(arr: arr)

a.sort(arr.count, dir: 1)

{{out}}

<pre>

flip(0.. 2): [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

</pre>

 

=={{header|Tcl}}==

# Some simple helper procedures

proc flip {nlist n} {

}

return $nlist

Demonstrate (with debug mode enabled so it prints intermediate states):

Output:

<pre>

</pre>

As you can see, it took 12 flips.

 

=={{header|uBasic/4tH}}==

{{trans|C}}

n = FUNC (_InitArray)

PROC _ShowArray (n)

PRINT

=={{header|VBA}}==

 

'pancake sort

printarray A

End Sub

 

Sample output:

Final array:

0 1 3 5 7 8 9 10 23 50

</pre>

 

=={{header|zkl}}==

{{trans|Julia}}

foreach i in ([a.len()-1..1,-1]){

j := a.index((0).max(a[0,i+1])); // min for decending sort

}

a

Note: [offset,count] not [start,stop]

 

Finding the max index creates a partial list, which isn't good; if it matters use:

{{out}}<pre>L(1,2,3,4,5,6,7,8,9)</pre>