Sorting algorithms/Pancake sort: Difference between revisions

{{trans|Python}}

 

 

F pancakesort(&data)

print(‘Original List: ’data.join(‘ ’))

pancakesort(&data)

 

{{out}}

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program mergeSort64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

<pre>

Value : -5

sorted in +17 flips

Table sorted.

</pre>

 

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

Algorithm gleaned from [[Sorting_algorithms/Pancake_sort#Phix|Phix]] and that from [[Sorting_algorithms/Pancake_sort#Euphoria|Euphoria]]

 

script o

property lst : aList

set output to "Before: {" & pre & ("}" & linefeed & "After: {" & post & "}")

set AppleScript's text item delimiters to astid

 

{{output}}

 

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program pancakeSort.s */

.include "../affichage.inc"

 

 

=={{header|Arturo}}==

 

arr: new items

len: size arr

]

 

 

{{out}}

 

=={{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:

=={{header|Batch File}}==

{{trans|BASIC}}

:: Batch File Implementation

 

echo DONE^^!

{{Out}}

<pre>Initial Sequence:

 

=={{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 sharp|C#}}==

public static class PancakeSorter

{

}

}

 

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

ELENA 5.0 :

{{trans|C#}}

extension op

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>

 

=={{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|Haxe}}==

@:generic

inline private static function flip<T>(arr:Array<T>, num:Int) {

Sys.println('Sorted Strings: ' + stringArray);

}

 

{{out}}

 

=={{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}}==

/** Returns the index of the highest number in the range 0 until n. */

fun indexOfMax(n: Int): Int = (0 until n).maxByOrNull{ a[it] }!!

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

pancakeSort(a)

 

{{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]):

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

LMaxPosition[a_, n_] := With[{b = Take[a, n]}, First[Ordering[b, -1]]]

SetAttributes[Flip, HoldAll];

a

]

{{out}}

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

 

=={{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]) =

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

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #0000FF;">?</span> <span style="color: #000000;">s</span>

<span style="color: #0000FF;">?</span> <span style="color: #000000;">pancake_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>

{{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:'''

 

=={{header|Quackery}}==

 

[ 0 swap behead swap

[ dup i^ split nip

smallest i^ + flip

 

'''Testing in Quackery shell:'''

 

=={{header|Racket}}==

#lang racket

 

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

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

 

=={{header|Raku}}==

(formerly Perl 6)

my $endpoint = @a.end;

while $endpoint > 0 and not [<] @a {

say 'input = ' ~ @data;

say 'output = ' ~ @data.&pancake_sort;

 

Output:<pre>input = 6 7 2 1 8 9 5 3 4

 

=={{header|REXX}}==

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

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

end /*j*/

call panFlip ?; call panFlip n

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

 

 

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

=={{header|Tailspin}}==

Simplest version, bubblesort style

templates pancakeSort

sink flip

when <2..> do

@pancakeSort.stack(1..$): $@pancakeSort.stack($..1:-1)...;

'$@pancakeSort.stack;$#10;' -> !OUT::write

end flip

sink fixTop

 

[6,7,2,1,8,9,5,3,4] -> pancakeSort -> !OUT::write

{{out}}

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

 

=={{header|Transd}}==

#lang transd

 

(textout vint "\n")

))

<pre>

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

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

{{trans|C}}

n = FUNC (_InitArray)

PROC _ShowArray (n)

PRINT

 

=={{header|UNIX Shell}}==

This takes advantage of the semi-standard UNIX utility <tt>shuf</tt> to randomize the initial array.

 

main() {

local stack

}

 

 

{{Out}}

 

=={{header|VBA}}==

 

'pancake sort

printarray A

End Sub

 

Sample output:

{{trans|Go}}

{{libheader|Wren-sort}}

 

class Pancake {

flip(r) {

for (l in 0...r) {

r = r - 1

}

System.print("unsorted: %(p)")

p.sort()

 

{{out}}

unsorted: [31, 41, 59, 26, 53, 58, 97, 93, 23, 84]

sorted : [23, 26, 31, 41, 53, 58, 59, 84, 93, 97]

</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>