Sorting algorithms/Pancake sort: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(Added AppleScript.) |
m (→{{header|Wren}}: Minor tidy) |
||
(26 intermediate revisions by 16 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 369 ⟶ 512:
Algorithm gleaned from [[Sorting_algorithms/Pancake_sort#Phix|Phix]] and that from [[Sorting_algorithms/Pancake_sort#Euphoria|Euphoria]]
<
script o
property lst : aList
Line 421 ⟶ 564:
set output to "Before: {" & pre & ("}" & linefeed & "After: {" & post & "}")
set AppleScript's text item delimiters to astid
return output</
{{output}}
<
After: {3, 11, 12, 18, 23, 23, 26, 27, 38, 39, 40, 40, 41, 43, 58, 59, 69, 72, 74, 91}"</
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program pancakeSort.s */
Line 630 ⟶ 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 681 ⟶ 850:
Return, List
}
</syntaxhighlight>
=={{header|BASIC}}==
Line 687 ⟶ 856:
{{works with|QBasic}}
<
DIM nums(9) AS INTEGER
Line 732 ⟶ 901:
PRINT
END IF
NEXT</
Sample output:
Line 753 ⟶ 922:
This is a graphical variation of the above.
<
CONST delay = .1 'controls display speed
Line 807 ⟶ 976:
ttmp = TIMER
DO WHILE TIMER < ttmp + delay: LOOP
RETURN</
Sample output:
Line 815 ⟶ 984:
=={{header|Batch File}}==
{{trans|BASIC}}
<
:: Batch File Implementation
Line 891 ⟶ 1,060:
echo DONE^^!
exit /b 0</
{{Out}}
<pre>Initial Sequence:
Line 917 ⟶ 1,086:
=={{header|BBC BASIC}}==
<
test() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
PROCpancakesort(test())
Line 948 ⟶ 1,117:
SWAP a(i%), a(n%-i%)
NEXT
ENDPROC</
'''Output:'''
<pre>
Line 956 ⟶ 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 997 ⟶ 1,166:
return moves;
}</
Where do_flip() is a simple function to flip a part of an array:
<
{
int swap;
Line 1,010 ⟶ 1,179:
list[num]=swap;
}
}</
'''Testing the function:'''
<
{
//Just need some random numbers. I chose <100
Line 1,032 ⟶ 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,077 ⟶ 1,246:
}
}
</syntaxhighlight>
=={{header|C++}}==
<
#include <iostream>
#include <iterator>
Line 1,129 ⟶ 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,144 ⟶ 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,157 ⟶ 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,191 ⟶ 1,360:
data.pancakeSort!true;
data.writeln;
}</
{{out}}
<pre>With: 769248135 doflip 3
Line 1,208 ⟶ 1,377:
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
PANCAKE_SORT [G -> COMPARABLE]
Line 1,314 ⟶ 1,483:
end
</syntaxhighlight>
Test:
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 1,350 ⟶ 1,519:
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,360 ⟶ 1,529:
ELENA 5.0 :
{{trans|C#}}
<
extension op
Line 1,426 ⟶ 1,595:
console.printLine("before:", list.asEnumerable());
console.printLine("after :", list.pancakeSort().asEnumerable())
}</
{{out}}
<pre>
Line 1,434 ⟶ 1,603:
=={{header|Elixir}}==
<
def pancake_sort(list) when is_list(list), do: pancake_sort(list, length(list))
Line 1,460 ⟶ 1,629:
IO.inspect list = Enum.shuffle(1..9)
IO.inspect Sort.pancake_sort(list)</
{{out}}
Line 1,469 ⟶ 1,638:
=={{header|Euphoria}}==
<
object temp
for i = 1 to n/2 do
Line 1,502 ⟶ 1,671:
? s
? pancake_sort(s)</
Output:
Line 1,510 ⟶ 1,679:
=={{header|F_Sharp|F#}}==
<
let show data = data |> Array.iter (printf "%d ") ; printfn ""
Line 1,528 ⟶ 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,538 ⟶ 1,707:
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
implicit none
Line 1,574 ⟶ 1,743:
end subroutine
end program Pancake_Demo</
Output:
<pre>
Line 1,593 ⟶ 1,762:
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
' for boundry checks on array's compile with: fbc -s console -exx
Line 1,696 ⟶ 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,717 ⟶ 1,886:
=={{header|Go}}==
<
import "fmt"
Line 1,750 ⟶ 1,919:
a[l], a[r] = a[r], a[l]
}
}</
Output:
<pre>
Line 1,759 ⟶ 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,774 ⟶ 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,785 ⟶ 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,800 ⟶ 1,969:
=={{header|Haskell}}==
<
import Control.Arrow
import Control.Monad
Line 1,813 ⟶ 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,866 ⟶ 2,035:
Sys.println('Sorted Strings: ' + stringArray);
}
}</
{{out}}
Line 1,879 ⟶ 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,919 ⟶ 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,948 ⟶ 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,965 ⟶ 2,134:
=={{header|Java}}==
<
public class PancakeSort
{
Line 2,047 ⟶ 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,065 ⟶ 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,100 ⟶ 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,126 ⟶ 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,151 ⟶ 2,368:
v = rand(-10:10, 10)
println("# unordered: $v\n -> ordered: ", pancakesort!(v))</
{{out}}
Line 2,158 ⟶ 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,220 ⟶ 2,421:
=={{header|Lua}}==
<
math.randomseed(os.time())
numList = {step = 0, sorted = 0}
Line 2,285 ⟶ 2,486:
numList:show()
until numList:isSorted()
</syntaxhighlight>
{{out}}
<pre>Initial state: -67 61 80 47 21 74 43 22 66 -66
Line 2,306 ⟶ 2,507:
=={{header|Maple}}==
<
local start, temp, icopy;
temp, start, icopy := 0,1,i:
Line 2,335 ⟶ 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,349 ⟶ 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,374 ⟶ 2,579:
=={{header|MATLAB}} / {{header|Octave}}==
<
for i = (numel(list):-1:2)
Line 2,401 ⟶ 2,606:
end
end %for
end %pancakeSort</
Sample Usage:
<
ans =
6 5 4 3 2 1</
=={{header|MAXScript}}==
<
(
local new = #()
Line 2,439 ⟶ 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,531 ⟶ 2,736:
return clist
</syntaxhighlight>
{{out}}
<pre>
Line 2,554 ⟶ 2,759:
=={{header|Nim}}==
<
proc pancakeSort[T](list: var openarray[T]) =
Line 2,579 ⟶ 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,626 ⟶ 2,831:
print_list res;
Printf.printf " sorted in %d loops\n" n;
;;</
=={{header|PARI/GP}}==
<
my(top=#v);
while(top>1,
Line 2,648 ⟶ 2,853:
);
v
};</
=={{header|Pascal}}==
<
procedure flip(var b: array of integer; last: integer);
Line 2,715 ⟶ 2,920:
end;
writeln;
end.</
Output:
<pre>:>./PancakeSort
Line 2,725 ⟶ 2,930:
=={{header|Perl}}==
<
my @x = @_;
for my $idx (0 .. $#x - 1) {
Line 2,743 ⟶ 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,749 ⟶ 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,784 ⟶ 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,814 ⟶ 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,850 ⟶ 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,863 ⟶ 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,903 ⟶ 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,949 ⟶ 3,174:
Print(#CRLF$+#CRLF$+"Press ENTER to quit."): Input()
CloseConsole()
EndIf</
'''Output can look like
Line 2,960 ⟶ 3,185:
=={{header|Python}}==
'''The function:'''
<
def pancakesort(data):
Line 2,979 ⟶ 3,204:
% ( ' '.join(str(x) for x in data), size ))
data[:size] = reversed(data[:size])
if tutor: print()</
'''A test:'''
<
import random
Line 2,991 ⟶ 3,216:
print('Original List: %r' % ' '.join(data))
pancakesort(data)
print('Pancake Sorted List: %r' % ' '.join(data))</
'''Sample output:'''
Line 3,008 ⟶ 3,233:
=={{header|Quackery}}==
<
[ 0 swap behead swap
Line 3,021 ⟶ 3,246:
[ dup i^ split nip
smallest i^ + flip
i^ flip ] ] is pancakesort ( [ --> [ )</
'''Testing in Quackery shell:'''
Line 3,035 ⟶ 3,260:
=={{header|Racket}}==
<
#lang racket
Line 3,048 ⟶ 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 3,072 ⟶ 3,297:
say 'input = ' ~ @data;
say 'output = ' ~ @data.&pancake_sort;
</syntaxhighlight>
Output:<pre>input = 6 7 2 1 8 9 5 3 4
Line 3,079 ⟶ 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,098 ⟶ 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:}}
Line 3,200 ⟶ 3,425:
=={{header|Ring}}==
<
pancakeList = [6, 7, 8, 9, 2, 5, 3, 4, 1]
flag = 0
Line 3,230 ⟶ 3,455:
end
return A
</syntaxhighlight>
Output:
<pre>
Line 3,240 ⟶ 3,465:
=={{header|Ruby}}==
<
def pancake_sort!
num_flips = 0
Line 3,261 ⟶ 3,486:
p a = (1..9).to_a.shuffle
p a.pancake_sort!</
'''sample output:'''
Line 3,278 ⟶ 3,503:
=={{header|Rust}}==
<
let len = v.len();
// trivial case -- no flips
Line 3,319 ⟶ 3,544:
pancake_sort(&mut strings);
println!("After: {:?}", strings);
}</
=={{header|Sidef}}==
{{trans|Perl}}
<
for idx in ^(a.end) {
var min = idx
Line 3,336 ⟶ 3,561:
var arr = 10.of{ 100.irand }
say "Before: #{arr}"
say "After: #{pancake(arr)}"</
{{out}}
Line 3,346 ⟶ 3,571:
=={{header|Swift}}==
{{trans|Java}}
<
struct PancakeSort {
Line 3,411 ⟶ 3,636:
var a = PancakeSort(arr: arr)
a.sort(arr.count, dir: 1)
println(a.arr)</
{{out}}
<pre>
Line 3,425 ⟶ 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,451 ⟶ 3,712:
}
return $nlist
}</
Demonstrate (with debug mode enabled so it prints intermediate states):
<
Output:
<pre>
Line 3,471 ⟶ 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,541 ⟶ 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,612 ⟶ 4,011:
printarray A
End Sub
</syntaxhighlight>
Sample output:
Line 3,646 ⟶ 4,045:
{{trans|Go}}
{{libheader|Wren-sort}}
<
class Pancake {
Line 3,655 ⟶ 4,054:
flip(r) {
for (l in 0...r) {
r = r - 1
}
Line 3,677 ⟶ 4,074:
System.print("unsorted: %(p)")
p.sort()
System.print("sorted : %(p)")</
{{out}}
Line 3,683 ⟶ 4,080:
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,693 ⟶ 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>
|