Sorting algorithms/Pancake sort: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (Split three sentences.) |
m (→{{header|Wren}}: Minor tidy) |
||
(31 intermediate revisions by 19 users not shown) | |||
Line 27:
* Wikipedia article: [[wp:Pancake sorting|pancake sorting]].
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">V tutor = 1B
F pancakesort(&data)
I data.len <= 1
R
I :tutor
print()
L(size) (data.len .< 1).step(-1)
V maxindex = max(0 .< size, key' x -> @data[x])
I maxindex + 1 != size
I maxindex != 0
I :tutor
print(‘With: #. doflip #.’.format(data.map(x -> String(x)).join(‘ ’), maxindex + 1))
data.reverse_range(0 .< maxindex + 1)
I :tutor
print(‘With: #. doflip #.’.format(data.map(x -> String(x)).join(‘ ’), size))
data.reverse_range(0 .< size)
I :tutor
print()
V data = ‘6 7 2 1 8 9 5 3 4’.split(‘ ’)
print(‘Original List: ’data.join(‘ ’))
pancakesort(&data)
print(‘Pancake Sorted List: ’data.join(‘ ’))</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program mergeSort64.s */
Line 248 ⟶ 292:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
<pre>
Value : -5
Line 265 ⟶ 309:
Table sorted.
</pre>
=={{header|Action!}}==
<syntaxhighlight lang="action!">PROC PrintArray(INT ARRAY a INT size)
INT i
Put('[)
FOR i=0 TO size-1
DO
IF i>0 THEN Put(' ) FI
PrintI(a(i))
OD
Put(']) PutE()
RETURN
PROC Flip(INT ARRAY a INT last)
INT i,n,tmp
n=(last-1)/2
FOR i=0 TO n
DO
tmp=a(i)
a(i)=a(last-i)
a(last-i)=tmp
OD
RETURN
PROC PancakeSort(INT ARRAY a INT size)
INT i,j,maxpos
i=size-1
WHILE i>=0
DO
maxpos=i
FOR j=0 TO i-1
DO
IF a(j)>a(maxpos) THEN
maxpos=j
FI
OD
IF maxpos#i THEN
IF maxpos#0 THEN
Flip(a,maxpos)
FI
Flip(a,i)
FI
i==-1
OD
RETURN
PROC Test(INT ARRAY a INT size)
PrintE("Array before sort:")
PrintArray(a,size)
PancakeSort(a,size)
PrintE("Array after sort:")
PrintArray(a,size)
PutE()
RETURN
PROC Main()
INT ARRAY
a(10)=[1 4 65535 0 3 7 4 8 20 65530],
b(21)=[10 9 8 7 6 5 4 3 2 1 0
65535 65534 65533 65532 65531
65530 65529 65528 65527 65526],
c(8)=[101 102 103 104 105 106 107 108],
d(12)=[1 65535 1 65535 1 65535 1
65535 1 65535 1 65535]
Test(a,10)
Test(b,21)
Test(c,8)
Test(d,12)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Pancake_sort.png Screenshot from Atari 8-bit computer]
<pre>
Array before sort:
[1 4 -1 0 3 7 4 8 20 -6]
Array after sort:
[-6 -1 0 1 3 4 4 7 8 20]
Array before sort:
[10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10]
Array after sort:
[-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10]
Array before sort:
[101 102 103 104 105 106 107 108]
Array after sort:
[101 102 103 104 105 106 107 108]
Array before sort:
[1 -1 1 -1 1 -1 1 -1 1 -1 1 -1]
Array after sort:
[-1 -1 -1 -1 -1 -1 1 1 1 1 1 1]
</pre>
=={{header|Ada}}==
<
procedure Pancake_Sort is
generic
Line 311 ⟶ 454:
end loop;
Ada.Text_IO.New_Line;
end Pancake_Sort;</
Output:
Line 318 ⟶ 461:
=={{header|ALGOL 68}}==
{{trans|Euphoria}}
<
BEGIN
[UPB s]INT ss := s;
Line 359 ⟶ 502:
printf (($"unsorted: "10(g(4) )l$, s));
printf (($"sorted: "10(g(4) )l$, pancake sort(s)))
</syntaxhighlight>
{{out}}
<pre>Pancake sort demonstration
Line 365 ⟶ 508:
sorted: -47 -41 -26 -7 -4 -2 +8 +21 +31 +41
</pre>
=={{header|AppleScript}}==
Algorithm gleaned from [[Sorting_algorithms/Pancake_sort#Phix|Phix]] and that from [[Sorting_algorithms/Pancake_sort#Euphoria|Euphoria]]
<syntaxhighlight lang="applescript">on pancake_sort(aList)
script o
property lst : aList
property len : (count my lst)
on flip(n)
if (n < len) then
set my lst to (reverse of items 1 thru n of my lst) & (items (n + 1) thru len of my lst)
else
set my lst to reverse of my lst
end if
end flip
end script
repeat with i from (count o's lst) to 2 by -1
set maxIdx to 1
set maxVal to beginning of o's lst
repeat with j from 2 to i
tell item j of o's lst
if (it > maxVal) then
set maxIdx to j
set maxVal to it
end if
end tell
end repeat
(* Performancewise, there's little to choose between doing the two 'if' tests below every time and
occasionally flipping unnecessarily. The flips themselves are of of course a daft way to achieve:
set item maxIdx of o's lst to item i of o's lst
set item i of o's lst to maxVal
*)
-- if (maxIdx < i) then
-- if (maxIdx > 1) then ¬
o's flip(maxIdx)
o's flip(i)
-- end if
end repeat
return o's lst
end pancake_sort
-- Task code:
local pre, post, astid, output
set pre to {}
repeat 20 times
set end of pre to (random number 100)
end repeat
set post to pancake_sort(pre)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to ", "
set output to "Before: {" & pre & ("}" & linefeed & "After: {" & post & "}")
set AppleScript's text item delimiters to astid
return output</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">"Before: {23, 72, 40, 43, 91, 38, 23, 58, 26, 59, 12, 18, 27, 39, 69, 74, 11, 41, 3, 40}
After: {3, 11, 12, 18, 23, 23, 26, 27, 38, 39, 40, 40, 41, 43, 58, 59, 69, 72, 74, 91}"</syntaxhighlight>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program pancakeSort.s */
Line 568 ⟶ 773:
.include "../affichage.inc"
</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">pancakeSort: function [items][
arr: new items
len: size arr
loop (len-1)..1 'endIdx [
maxim: max slice arr 0 endIdx
maximIdx: index arr maxim
if maximIdx=endIdx -> continue
if maximIdx > 0 [
arr: (reverse slice arr 0 maximIdx) ++ slice arr maximIdx+1 (size arr)-1
]
arr: (reverse slice arr 0 endIdx) ++ slice arr endIdx+1 (size arr)-1
]
arr
]
print pancakeSort [3 1 2 8 5 7 9 4 6]</syntaxhighlight>
{{out}}
<pre>1 2 3 4 5 6 7 8 9</pre>
=={{header|AutoHotkey}}==
<
Loop { ; test loop
;---------------------------------------------------------------------------
Line 619 ⟶ 850:
Return, List
}
</syntaxhighlight>
=={{header|BASIC}}==
Line 625 ⟶ 856:
{{works with|QBasic}}
<
DIM nums(9) AS INTEGER
Line 670 ⟶ 901:
PRINT
END IF
NEXT</
Sample output:
Line 691 ⟶ 922:
This is a graphical variation of the above.
<
CONST delay = .1 'controls display speed
Line 745 ⟶ 976:
ttmp = TIMER
DO WHILE TIMER < ttmp + delay: LOOP
RETURN</
Sample output:
Line 753 ⟶ 984:
=={{header|Batch File}}==
{{trans|BASIC}}
<
:: Batch File Implementation
Line 829 ⟶ 1,060:
echo DONE^^!
exit /b 0</
{{Out}}
<pre>Initial Sequence:
Line 855 ⟶ 1,086:
=={{header|BBC BASIC}}==
<
test() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
PROCpancakesort(test())
Line 886 ⟶ 1,117:
SWAP a(i%), a(n%-i%)
NEXT
ENDPROC</
'''Output:'''
<pre>
Line 894 ⟶ 1,125:
=={{header|C}}==
'''The function that sorts:'''
<
{
//If it's less than 2 long, just return it as sorting isn't really needed...
Line 935 ⟶ 1,166:
return moves;
}</
Where do_flip() is a simple function to flip a part of an array:
<
{
int swap;
Line 948 ⟶ 1,179:
list[num]=swap;
}
}</
'''Testing the function:'''
<
{
//Just need some random numbers. I chose <100
Line 970 ⟶ 1,201:
print_array(list, 9);
printf(" - with a total of %d moves\n", moves);
}</
=={{header|C sharp|C#}}==
<
public static class PancakeSorter
{
Line 1,015 ⟶ 1,246:
}
}
</syntaxhighlight>
=={{header|C++}}==
<
#include <iostream>
#include <iterator>
Line 1,067 ⟶ 1,298:
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]
Line 1,082 ⟶ 1,313:
head (reverse torev)]
(cons mx (pancake-sort (concat (drop 1 head) (drop 1 tail))))))))
</syntaxhighlight>
=={{header|Common Lisp}}==
<
"A destructive version of Pancake Sort that works with either lists or arrays of numbers."
(defun flip (lst index)
Line 1,095 ⟶ 1,326:
(flip lst (1+ index)))
(flip lst i)
finally (return (coerce lst (type-of seq)))))</
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
#(1.0 2 3 4 5 6.5 7.5 8 9)</
=={{header|D}}==
{{trans|Python}}
<
void pancakeSort(bool tutor=false, T)(T[] data) {
Line 1,129 ⟶ 1,360:
data.pancakeSort!true;
data.writeln;
}</
{{out}}
<pre>With: 769248135 doflip 3
Line 1,146 ⟶ 1,377:
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
PANCAKE_SORT [G -> COMPARABLE]
Line 1,252 ⟶ 1,483:
end
</syntaxhighlight>
Test:
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 1,288 ⟶ 1,519:
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,298 ⟶ 1,529:
ELENA 5.0 :
{{trans|C#}}
<
extension op
Line 1,364 ⟶ 1,595:
console.printLine("before:", list.asEnumerable());
console.printLine("after :", list.pancakeSort().asEnumerable())
}</
{{out}}
<pre>
Line 1,372 ⟶ 1,603:
=={{header|Elixir}}==
<
def pancake_sort(list) when is_list(list), do: pancake_sort(list, length(list))
Line 1,398 ⟶ 1,629:
IO.inspect list = Enum.shuffle(1..9)
IO.inspect Sort.pancake_sort(list)</
{{out}}
Line 1,407 ⟶ 1,638:
=={{header|Euphoria}}==
<
object temp
for i = 1 to n/2 do
Line 1,440 ⟶ 1,671:
? s
? pancake_sort(s)</
Output:
Line 1,448 ⟶ 1,679:
=={{header|F_Sharp|F#}}==
<
let show data = data |> Array.iter (printf "%d ") ; printfn ""
Line 1,466 ⟶ 1,697:
loop partialSort (limit-1)
loop items ((Array.length items)-1)</
Usage: pancakeSort [|31; 41; 59; 26; 53; 58; 97; 93; 23; 84|] |> show
Line 1,476 ⟶ 1,707:
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
implicit none
Line 1,512 ⟶ 1,743:
end subroutine
end program Pancake_Demo</
Output:
<pre>
Line 1,531 ⟶ 1,762:
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
' for boundry checks on array's compile with: fbc -s console -exx
Line 1,634 ⟶ 1,865:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>unsorted -1 -4 1 6 7 5 2 -3 4 -5 -2 -6 0 3 -7
Line 1,655 ⟶ 1,886:
=={{header|Go}}==
<
import "fmt"
Line 1,688 ⟶ 1,919:
a[l], a[r] = a[r], a[l]
}
}</
Output:
<pre>
Line 1,697 ⟶ 1,928:
=={{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) } }
Line 1,712 ⟶ 1,943:
}
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 ()
Line 1,723 ⟶ 1,954:
println (pancakeSort([10.0, 10.00, 10, 1]))
println (pancakeSort([10.00, 10, 10.0, 1]))
println (pancakeSort([10.00, 10.0, 10, 1]))</
The use of decimals and integers that compare as equal demonstrates, but of course not '''prove''', that the sort is stable.
Line 1,738 ⟶ 1,969:
=={{header|Haskell}}==
<
import Control.Arrow
import Control.Monad
Line 1,751 ⟶ 1,982:
dopcs ([],rs) = rs
dopcs ([x],rs) = x:rs
dopcs (xs,rs) = dopcs $ (init &&& (:rs).last ) $ dblflipIt xs</
Example:
<
[0,1,2,2,3]</
=={{header|Haxe}}==
<
@:generic
inline private static function flip<T>(arr:Array<T>, num:Int) {
Line 1,804 ⟶ 2,035:
Sys.println('Sorted Strings: ' + stringArray);
}
}</
{{out}}
Line 1,817 ⟶ 2,048:
=={{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
Line 1,857 ⟶ 2,088:
every writes(" ["|right(!X,4)|" ]\n") # show X
return X
end</
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.
Line 1,886 ⟶ 2,117:
=={{header|J}}==
{{eff note|J|/:~}}
<
unsorted=: #~ 1 , [: >./\. 2 >/\ ]
FlDown=: flip 1 + (i. >./)@unsorted
FlipUp=: flip 1 >. [:+/>./\&|.@(< {.)
pancake=: FlipUp@FlDown^:_</
Example use:
<
1 0 8 7 4 6 3 5 2
0 1 2 3 4 5 6 7 8</
See the [[Talk:Sorting_algorithms/Pancake_sort#J_implementation|discussion page]] for illustrations of the other words.
Line 1,903 ⟶ 2,134:
=={{header|Java}}==
<
public class PancakeSort
{
Line 1,985 ⟶ 2,216:
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
Line 2,003 ⟶ 2,234:
flip(0..4): 7 6 5 4 3 2 1 8 9
flip(0..6): 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 </
===Using Java 8===
<syntaxhighlight lang="java">
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.stream.IntStream;
public final class PancakeSort {
public static void main(String[] aArgs) {
List<Integer> numbers = Arrays.asList( 1, 5, 4, 2, 3, 2, 8, 6, 7 );
System.out.println("Initial list: " + numbers);
pancakeSort(numbers);
}
private static void pancakeSort(List<Integer> aList) {
for ( int i = aList.size() - 1; i >= 0; i-- ) {
int index = IntStream.rangeClosed(0, i).boxed().max(Comparator.comparing(aList::get)).get();
if ( index != i ) {
flip(aList, index);
flip(aList, i);
}
}
}
private static void flip(List<Integer> aList, int aIndex) {
if ( aIndex > 0 ) {
Collections.reverse(aList.subList(0, aIndex + 1));
System.out.println("flip 0.." + aIndex + " --> " + aList);
}
}
}
</syntaxhighlight>
{{ out }}
<pre>
Initial list: [1, 5, 4, 2, 3, 2, 8, 6, 7]
flip 0..6 --> [8, 2, 3, 2, 4, 5, 1, 6, 7]
flip 0..8 --> [7, 6, 1, 5, 4, 2, 3, 2, 8]
flip 0..7 --> [2, 3, 2, 4, 5, 1, 6, 7, 8]
flip 0..4 --> [5, 4, 2, 3, 2, 1, 6, 7, 8]
flip 0..5 --> [1, 2, 3, 2, 4, 5, 6, 7, 8]
flip 0..2 --> [3, 2, 1, 2, 4, 5, 6, 7, 8]
flip 0..3 --> [2, 1, 2, 3, 4, 5, 6, 7, 8]
flip 0..2 --> [2, 1, 2, 3, 4, 5, 6, 7, 8]
flip 0..1 --> [1, 2, 2, 3, 4, 5, 6, 7, 8]
</pre>
=={{header|JavaScript}}==
<
for (var i = this.length - 1; i >= 1; i--) {
// find the index of the largest element not yet sorted
Line 2,038 ⟶ 2,319:
}
ary = [7,6,5,9,8,4,3,1,2,0]
sorted = ary.concat().pancake_sort();</
=={{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):
Line 2,064 ⟶ 2,345:
| if ($i == $max) then .
else flip($max) | flip($i)
end ) ;</
'''Example''':
<
| pancakeSort</
{{out}}
<
[null,0,0.5,1,1,2,3,[1],[2],{"a":2},{"b":1}]</
=={{header|Julia}}==
<syntaxhighlight lang="julia">function pancakesort!(arr::Vector{<:Real})
len = length(arr)
if len < 2 return arr end
for i in len:-1:2
j =
if i == j continue end
arr[1:j] = reverse(arr[1:j])
Line 2,089 ⟶ 2,368:
v = rand(-10:10, 10)
println("# unordered: $v\n -> ordered: ", pancakesort!(v))</
{{out}}
Line 2,096 ⟶ 2,375:
=={{header|Kotlin}}==
<syntaxhighlight lang="kotlin">fun pancakeSort(a: IntArray) {
/** Returns the index of the highest number in the range 0 until n. */
fun indexOfMax(n: Int): Int = (0 until n).maxByOrNull{ a[it] }!!
/** Flips the elements in the range 0 .. n. */
fun flip(index: Int) {
a.reverse(0, index + 1)
}
for (n in a.size downTo 2) { // successively reduce size of array by 1
val index = indexOfMax(n) // find index of largest
println("${a.contentToString()} after flipping first ${index + 1}")
}
flip(n - 1) // move largest to end
println("${a.contentToString()} after flipping first $n")
}
}
}
fun main(
val a = intArrayOf(7, 6, 9, 2, 4, 8, 1, 3, 5)
println("${a.contentToString()} initially")
}</
{{out}}
Line 2,158 ⟶ 2,421:
=={{header|Lua}}==
<
math.randomseed(os.time())
numList = {step = 0, sorted = 0}
Line 2,223 ⟶ 2,486:
numList:show()
until numList:isSorted()
</syntaxhighlight>
{{out}}
<pre>Initial state: -67 61 80 47 21 74 43 22 66 -66
Line 2,244 ⟶ 2,507:
=={{header|Maple}}==
<
local start, temp, icopy;
temp, start, icopy := 0,1,i:
Line 2,273 ⟶ 2,536:
end do:
print(arr);
end proc:</
{{Out|Example}}
Input: arr := Array([17,3,72,0,36,2,3,8,40,1]):
Line 2,287 ⟶ 2,550:
[0, 1, 2, 3, 3, 8, 17, 36, 40, 72]</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[LMaxPosition, Flip, pancakeSort]
LMaxPosition[a_, n_] := With[{b = Take[a, n]}, First[Ordering[b, -1]]]
SetAttributes[Flip,
Flip[a_] := Set[a, Reverse[a]]
pancakeSort[
Do[
If[lm < n,
Flip[a[[;; lm]]];
Flip[a[[;; n]]];
];
,
];
a
]
pancakeSort[{6, 7, 8, 9, 2, 5, 3, 4, 1}]</syntaxhighlight>
{{out}}
<pre>{9,8,7,6,2,5,3,4,1}
{1,4,3,5,2,6,7,8,9}
{5,3,4,1,2,6,7,8,9}
Line 2,312 ⟶ 2,579:
=={{header|MATLAB}} / {{header|Octave}}==
<
for i = (numel(list):-1:2)
Line 2,339 ⟶ 2,606:
end
end %for
end %pancakeSort</
Sample Usage:
<
ans =
6 5 4 3 2 1</
=={{header|MAXScript}}==
<
(
local new = #()
Line 2,377 ⟶ 2,644:
return arr
)
)</
Output:
<syntaxhighlight lang="maxscript">
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)
</syntaxhighlight>
=={{header|NetRexx}}==
Sorts integers, decimal numbers and strings because they're all the same to NetRexx.
<
options replace format comments java crossref symbols nobinary
Line 2,469 ⟶ 2,736:
return clist
</syntaxhighlight>
{{out}}
<pre>
Line 2,492 ⟶ 2,759:
=={{header|Nim}}==
<
proc pancakeSort[T](list: var openarray[T]) =
Line 2,502 ⟶ 2,769:
for i in countdown(length, 2):
var maxNumPos = 0
for a in 0 ..
if list[a] > list[maxNumPos]:
maxNumPos = a
Line 2,517 ⟶ 2,784:
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
pancakeSort a
echo a</
Output:
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>
=={{header|OCaml}}==
<
| [] -> (true)
| x::y::_ when x > y -> (false)
Line 2,564 ⟶ 2,831:
print_list res;
Printf.printf " sorted in %d loops\n" n;
;;</
=={{header|PARI/GP}}==
<
my(top=#v);
while(top>1,
Line 2,586 ⟶ 2,853:
);
v
};</
=={{header|Pascal}}==
<
procedure flip(var b: array of integer; last: integer);
Line 2,653 ⟶ 2,920:
end;
writeln;
end.</
Output:
<pre>:>./PancakeSort
Line 2,663 ⟶ 2,930:
=={{header|Perl}}==
<
my @x = @_;
for my $idx (0 .. $#x - 1) {
Line 2,681 ⟶ 2,948:
@a = pancake(@a);
print "After @a\n";
</syntaxhighlight>
Sample output:
<pre>Before 57 37 35 35 22 58 70 53 77 15
Line 2,687 ⟶ 2,954:
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">pancake_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">2</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">largest</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;"><</span><span style="color: #000000;">i</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">m</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">))</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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,722 ⟶ 2,980:
{1,2,3,4,5,6,7,8,9,10}
</pre>
=={{header|Picat}}==
<syntaxhighlight lang="picat">go =>
Nums = [6,7,8,9,2,5,3,4,1],
println(Nums),
Sorted = pancake_sort(Nums),
println(Sorted),
nl.
pancake_sort(L) = L =>
T = L.len,
while (T > 1)
Ix = argmax(L[1..T]),
if Ix == 1 then
L := L[1..T].reverse ++ L.slice(T+1),
T := T-1
else
L := L[1..Ix].reverse ++ L.slice(Ix+1)
end
end.
% Get the index of the (first) maximal value in L
argmax(L) = MaxIx =>
Max = max(L),
MaxIx = [I : I in 1..L.length, L[I] == Max].first.</syntaxhighlight>
{{out}}
<pre>[6,7,8,9,2,5,3,4,1]
[1,2,3,4,5,6,7,8,9]</pre>
=={{header|PicoLisp}}==
<
(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))) ) ) )</
Output:
<pre>: (trace 'flip)
Line 2,752 ⟶ 3,039:
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
pancake_sort: procedure options (main); /* 23 April 2009 */
declare a(10) fixed, (i, n, loc) fixed binary;
Line 2,788 ⟶ 3,075:
end pancake_sort;
</syntaxhighlight>
Output:
<syntaxhighlight lang="text">
3 9 2 7 10 1 8 5 4 6
6 4 5 8 1 3 9 2 7 10
Line 2,801 ⟶ 3,088:
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
</syntaxhighlight>
=={{header|PowerShell}}==
<
{
$data=$indata.Clone()
Line 2,841 ⟶ 3,128:
}
$l = 100; PancakeSort ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( 0, $l - 1 ) } )</
=={{header|PureBasic}}==
<
Define i, j, k, Loops
Dim Pile(9)
Line 2,887 ⟶ 3,174:
Print(#CRLF$+#CRLF$+"Press ENTER to quit."): Input()
CloseConsole()
EndIf</
'''Output can look like
Line 2,898 ⟶ 3,185:
=={{header|Python}}==
'''The function:'''
<
def pancakesort(data):
Line 2,917 ⟶ 3,204:
% ( ' '.join(str(x) for x in data), size ))
data[:size] = reversed(data[:size])
if tutor: print()</
'''A test:'''
<
import random
Line 2,929 ⟶ 3,216:
print('Original List: %r' % ' '.join(data))
pancakesort(data)
print('Pancake Sorted List: %r' % ' '.join(data))</
'''Sample output:'''
Line 2,944 ⟶ 3,231:
Pancake Sorted List: '1 2 3 4 5 6 7 8 9'</pre>
=={{header|Quackery}}==
<syntaxhighlight lang="quackery">[ split reverse join ] is flip ( [ n --> [ )
[ 0 swap behead swap
witheach
[ 2dup > iff
[ nip nip
i^ 1+ swap ]
else drop ]
drop ] is smallest ( [ --> n )
[ dup size times
[ dup i^ split nip
smallest i^ + flip
i^ flip ] ] is pancakesort ( [ --> [ )</syntaxhighlight>
'''Testing in Quackery shell:'''
<pre>/O> [] 23 times [ 10 random join ]
... say "Before: " dup echo cr
... say " After: " pancakesort echo cr
...
Before: [ 1 2 1 5 5 9 7 1 2 3 9 1 9 2 5 0 5 2 6 0 8 3 2 ]
After: [ 0 0 1 1 1 1 2 2 2 2 2 3 3 5 5 5 5 6 7 8 9 9 9 ]
Stack empty.</pre>
=={{header|Racket}}==
<
#lang racket
Line 2,959 ⟶ 3,273:
(pancake-sort (shuffle (range 0 10)))
;; => '(0 1 2 3 4 5 6 7 8 9)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
my $endpoint = @a.end;
while $endpoint > 0 and not [<] @a {
Line 2,983 ⟶ 3,297:
say 'input = ' ~ @data;
say 'output = ' ~ @data.&pancake_sort;
</syntaxhighlight>
Output:<pre>input = 6 7 2 1 8 9 5 3 4
Line 2,990 ⟶ 3,304:
=={{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. */
exit
/*──────────────────────────────────────────────────────────────────────────────────────*/
panFlip: parse arg y; do i=1 for (y+1)%2; yi=y-i+1; _=@.i; @.i=@.yi; @.yi=_; end; return
show: do k=1 for #; say @element right(k,length(#)) arg(1)':' right(@.k,9); end; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
Line 3,009 ⟶ 3,324:
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
$= bp fibs;
return /* [↑] populate the @. array with #s*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
pancakeSort: procedure expose @.; parse arg
!= @.j;
end /*j*/
{{out|output|text= when using the internally generated numbers:}}
<small>(Shown at three-quarter size.)</small>
<pre style="font-size:75%;height:
element 1 before sort: 2
element 2 before sort: 17
Line 3,111 ⟶ 3,425:
=={{header|Ring}}==
<
pancakeList = [6, 7, 8, 9, 2, 5, 3, 4, 1]
flag = 0
Line 3,141 ⟶ 3,455:
end
return A
</syntaxhighlight>
Output:
<pre>
Line 3,151 ⟶ 3,465:
=={{header|Ruby}}==
<
def pancake_sort!
num_flips = 0
Line 3,172 ⟶ 3,486:
p a = (1..9).to_a.shuffle
p a.pancake_sort!</
'''sample output:'''
Line 3,189 ⟶ 3,503:
=={{header|Rust}}==
<
let len = v.len();
// trivial case -- no flips
Line 3,230 ⟶ 3,544:
pancake_sort(&mut strings);
println!("After: {:?}", strings);
}</
=={{header|Sidef}}==
{{trans|Perl}}
<
for idx in ^(a.end) {
var min = idx
Line 3,247 ⟶ 3,561:
var arr = 10.of{ 100.irand }
say "Before: #{arr}"
say "After: #{pancake(arr)}"</
{{out}}
Line 3,257 ⟶ 3,571:
=={{header|Swift}}==
{{trans|Java}}
<
struct PancakeSort {
Line 3,322 ⟶ 3,636:
var a = PancakeSort(arr: arr)
a.sort(arr.count, dir: 1)
println(a.arr)</
{{out}}
<pre>
Line 3,336 ⟶ 3,650:
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|Tailspin}}==
Simplest version, bubblesort style
<syntaxhighlight lang="tailspin">
templates pancakeSort
@: {stack: $, flips: 0"1"};
sink flip
when <2..> do
@pancakeSort.stack(1..$): $@pancakeSort.stack($..1:-1)...;
'$@pancakeSort.stack;$#10;' -> !OUT::write
@pancakeSort.flips: $@pancakeSort.flips + 1"1";
end flip
sink fixTop
@: 1;
2..$ -> #
$ -> \(when <~=$@fixTop> do $@fixTop -> !flip $ -> !flip \) -> !VOID
when <?($@pancakeSort.stack($) <$@pancakeSort.stack($@)..>)> do @: $;
end fixTop
$::length..2:-1 -> !fixTop
$@ !
end pancakeSort
[6,7,2,1,8,9,5,3,4] -> pancakeSort -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
[9, 8, 1, 2, 7, 6, 5, 3, 4]
[4, 3, 5, 6, 7, 2, 1, 8, 9]
[7, 6, 5, 3, 4, 2, 1, 8, 9]
[1, 2, 4, 3, 5, 6, 7, 8, 9]
[4, 2, 1, 3, 5, 6, 7, 8, 9]
[3, 1, 2, 4, 5, 6, 7, 8, 9]
[2, 1, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
{flips=8, stack=[1, 2, 3, 4, 5, 6, 7, 8, 9]}
</pre>
=={{header|Tcl}}==
<
# Some simple helper procedures
proc flip {nlist n} {
Line 3,362 ⟶ 3,712:
}
return $nlist
}</
Demonstrate (with debug mode enabled so it prints intermediate states):
<
Output:
<pre>
Line 3,382 ⟶ 3,732:
</pre>
As you can see, it took 12 flips.
=={{header|Transd}}==
<syntaxhighlight lang="scheme">
#lang transd
MainModule: {
vint: [ 9, 0, 5, 10, 3, -3, -1, 8, -7, -4, -2, -6, 2, 4, 6, -10, 7, -8, -5, 1, -9],
_start: (λ (with n (- (size vint) 1) m 0
(textout vint "\n")
(while n
(= m (max-element-idx vint Range(0 (+ n 1))))
(if (neq m n)
(if m (reverse vint Range(0 (+ m 1))))
(reverse vint Range(0 (+ n 1))))
(-= n 1)
)
(textout vint "\n")
))
}</syntaxhighlight>{{out}}
<pre>
[9, 0, 5, 10, 3, -3, -1, 8, -7, -4, -2, -6, 2, 4, 6, -10, 7, -8, -5, 1, -9]
[-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
</pre>
=={{header|uBasic/4tH}}==
{{trans|C}}
<syntaxhighlight lang="text">PRINT "Pancake sort:"
n = FUNC (_InitArray)
PROC _ShowArray (n)
Line 3,452 ⟶ 3,826:
PRINT
RETURN</
=={{header|UNIX Shell}}==
{{works with|Bourne Again Shell}}
This takes advantage of the semi-standard UNIX utility <tt>shuf</tt> to randomize the initial array.
<syntaxhighlight lang="sh">#!/usr/bin/env bash
main() {
local stack
local -i n m i
if (( $# )); then
stack=("$@")
else
stack=($(printf '%s\n' {0..9} | shuf))
fi
print_stack 0 "${stack[@]}"
# start by looking at whole stack
(( n = ${#stack[@]} ))
# keep going until we're all sorted
while (( n > 0 )); do
# shrink the stack until its bottom is not the right size
while (( n > 0 && ${stack[n-1]} == n-1 )); do
(( n-=1 ))
done
# if we got to the top we're done
if (( n == 0 )); then
break
fi
# find the index of the largest pancake in the unsorted stack
m=0
for (( i=1; i < n-1; ++i )); do
if (( ${stack[i]} > ${stack[m]} )); then
(( m = i ))
fi
done
# if it's not on top, flip to get it there
if (( m > 0 )); then
stack=( $(flip "$(( m + 1 ))" "${stack[@]}") )
print_stack "$(( m + 1))" "${stack[@]}"
fi
# now flip the top to the bottom
stack=( $(flip "$n" "${stack[@]}" ) )
print_stack "$n" "${stack[@]}"
# and move up
(( n -= 1 ))
done
print_stack 0 "${stack[@]}"
}
# display the stack, optionally with brackets around a prefix
print_stack() {
local prefix=$1
shift
if (( prefix )); then
printf '[%s' "$1"
if (( prefix > 1 )); then
printf ',%s' "${@:2:prefix-1}"
fi
printf ']'
else
printf ' '
fi
if (( prefix < $# )); then
printf '%s' "${@:prefix+1:1}"
if (( prefix+1 < $# )); then
printf ',%s' "${@:prefix+2:$#-prefix-1}"
fi
fi
printf '\n'
}
# reverse the first N elements of an array
flip() {
local -i size end midpoint i
local stack temp
size=$1
shift
stack=( "$@" )
if (( size > 1 )); then
(( end = size - 1 ))
(( midpoint = size/2 + size % 2 ))
for (( i=0; i<midpoint; ++i )); do
temp=${stack[i]}
stack[i]=${stack[size-1-i]}
stack[size-1-i]=$temp
done
fi
printf '%s\n' "${stack[@]}"
}
main "$@"</syntaxhighlight>
{{Out}}
Sample run:
<pre> 3,0,9,7,6,1,2,5,4,8
[9,0,3]7,6,1,2,5,4,8
[8,4,5,2,1,6,7,3,0,9]
[0,3,7,6,1,2,5,4,8]9
[7,3,0]6,1,2,5,4,8,9
[4,5,2,1,6,0,3,7]8,9
[6,1,2,5,4]0,3,7,8,9
[3,0,4,5,2,1,6]7,8,9
[5,4,0,3]2,1,6,7,8,9
[1,2,3,0,4,5]6,7,8,9
[3,2,1]0,4,5,6,7,8,9
[0,1,2,3]4,5,6,7,8,9
0,1,2,3,4,5,6,7,8,9</pre>
=={{header|VBA}}==
<syntaxhighlight lang="vb">
'pancake sort
Line 3,523 ⟶ 4,011:
printarray A
End Sub
</syntaxhighlight>
Sample output:
Line 3,552 ⟶ 4,040:
Final array:
0 1 3 5 7 8 9 10 23 50
</pre>
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-sort}}
<syntaxhighlight lang="wren">import "./sort" for Find
class Pancake {
construct new(a) {
_a = a.toList
}
flip(r) {
for (l in 0...r) {
_a.swap(r, l)
r = r - 1
}
}
sort() {
for (uns in _a.count-1..1) {
var h = Find.highest(_a[0..uns])
var lx = h[2][0]
flip(lx)
flip(uns)
}
}
toString { _a.toString }
}
var p = Pancake.new([31, 41, 59, 26, 53, 58, 97, 93, 23, 84])
System.print("unsorted: %(p)")
p.sort()
System.print("sorted : %(p)")</syntaxhighlight>
{{out}}
<pre>
unsorted: [31, 41, 59, 26, 53, 58, 97, 93, 23, 84]
sorted : [23, 26, 31, 41, 53, 58, 59, 84, 93, 97]
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">proc Show(A, N); \Show items in array A with size N
int A, N, I;
[for I:= 0 to N-1 do
[IntOut(0, A(I)); ChOut(0, ^ )];
CrLf(0);
];
proc Sort(A, N); \Pancake sort array A with size N
int A, N, I, J, JMax;
proc Flip(K); \Reverse order of array items from 0 to K
int K, L, T;
[L:= 0;
while L < K do
[T:= A(L); A(L):= A(K); A(K):= T; \swap
K:= K-1;
L:= L+1;
];
Show(A, N); \show result of reversed items
];
[for I:= N-1 downto 1 do
[JMax:= 0;
for J:= 1 to I do
if A(J) > A(JMax) then JMax:= J;
if JMax < I then
[Flip(JMax);
Flip(I);
];
];
];
int A, N;
[A:= [6, 7, 2, 1, 8, 9, 5, 3, 4];
N:= 9;
Show(A, N); \show initial
Sort(A, N);
]</syntaxhighlight>
{{out}}
<pre>
6 7 2 1 8 9 5 3 4
9 8 1 2 7 6 5 3 4
4 3 5 6 7 2 1 8 9
7 6 5 3 4 2 1 8 9
1 2 4 3 5 6 7 8 9
4 2 1 3 5 6 7 8 9
3 1 2 4 5 6 7 8 9
3 1 2 4 5 6 7 8 9
2 1 3 4 5 6 7 8 9
2 1 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
</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
Line 3,562 ⟶ 4,144:
}
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>
|