Sorting algorithms/Patience sort: Difference between revisions
Content deleted Content added
Thundergnat (talk | contribs) m syntax highlighting fixup automation |
|||
Line 13: | Line 13: | ||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
< |
<syntaxhighlight lang="11l">F patience_sort(&arr) |
||
I arr.len < 2 {R} |
I arr.len < 2 {R} |
||
Line 48: | Line 48: | ||
V sArr = [‘dog’, ‘cow’, ‘cat’, ‘ape’, ‘ant’, ‘man’, ‘pig’, ‘ass’, ‘gnu’] |
V sArr = [‘dog’, ‘cow’, ‘cat’, ‘ape’, ‘ant’, ‘man’, ‘pig’, ‘ass’, ‘gnu’] |
||
patience_sort(&sArr) |
patience_sort(&sArr) |
||
print(sArr)</ |
print(sArr)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 59: | Line 59: | ||
=={{header|AArch64 Assembly}}== |
=={{header|AArch64 Assembly}}== |
||
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |
||
<syntaxhighlight lang="aarch64 assembly"> |
|||
<lang AArch64 Assembly> |
|||
/* ARM assembly AARCH64 Raspberry PI 3B */ |
/* ARM assembly AARCH64 Raspberry PI 3B */ |
||
/* program patienceSort64.s */ |
/* program patienceSort64.s */ |
||
Line 422: | Line 422: | ||
/* for this file see task include a file in language AArch64 assembly */ |
/* for this file see task include a file in language AArch64 assembly */ |
||
.include "../includeARM64.inc" |
.include "../includeARM64.inc" |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
Line 432: | Line 432: | ||
< |
<syntaxhighlight lang="ada">---------------------------------------------------------------------- |
||
with Ada.Text_IO; |
with Ada.Text_IO; |
||
Line 719: | Line 719: | ||
end patience_sort_task; |
end patience_sort_task; |
||
----------------------------------------------------------------------</ |
----------------------------------------------------------------------</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 727: | Line 727: | ||
=={{header|AppleScript}}== |
=={{header|AppleScript}}== |
||
< |
<syntaxhighlight lang="applescript">-- In-place patience sort. |
||
on patienceSort(theList, l, r) -- Sort items l thru r of theList. |
on patienceSort(theList, l, r) -- Sort items l thru r of theList. |
||
set listLen to (count theList) |
set listLen to (count theList) |
||
Line 786: | Line 786: | ||
set aList to {62, 86, 59, 65, 92, 85, 71, 71, 27, -52, 67, 59, 65, 80, 3, 65, 2, 46, 83, 72, 47, 5, 26, 18, 63} |
set aList to {62, 86, 59, 65, 92, 85, 71, 71, 27, -52, 67, 59, 65, 80, 3, 65, 2, 46, 83, 72, 47, 5, 26, 18, 63} |
||
sort(aList, 1, -1) |
sort(aList, 1, -1) |
||
return aList</ |
return aList</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
< |
<syntaxhighlight lang="applescript">{-52, 2, 3, 5, 18, 26, 27, 46, 47, 59, 59, 62, 63, 65, 65, 65, 67, 71, 71, 72, 80, 83, 85, 86, 92}</syntaxhighlight> |
||
=={{header|ARM Assembly}}== |
=={{header|ARM Assembly}}== |
||
{{works with|as|Raspberry Pi}} |
{{works with|as|Raspberry Pi}} |
||
<syntaxhighlight lang="arm assembly"> |
|||
<lang ARM Assembly> |
|||
/* ARM assembly Raspberry PI */ |
/* ARM assembly Raspberry PI */ |
||
/* program patienceSort.s */ |
/* program patienceSort.s */ |
||
Line 1,121: | Line 1,121: | ||
/***************************************************/ |
/***************************************************/ |
||
.include "../affichage.inc" |
.include "../affichage.inc" |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|ATS}}== |
=={{header|ATS}}== |
||
Line 1,131: | Line 1,131: | ||
The sort routine returns an array of indices into the original array, which is left unmodified. |
The sort routine returns an array of indices into the original array, which is left unmodified. |
||
< |
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*) |
||
#include "share/atspre_staload.hats" |
#include "share/atspre_staload.hats" |
||
Line 1,810: | Line 1,810: | ||
end |
end |
||
(*------------------------------------------------------------------*)</ |
(*------------------------------------------------------------------*)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,823: | Line 1,823: | ||
This version of the sort (which I derived from the first) has a more primitive "core" implementation, and a wrapper around that. The "core" requires that the user pass workspace to it (much as Fortran 77 procedures often do). The wrapper uses stack storage for the workspaces, if the sorted subarray is small; otherwise it uses malloc. One may be interested in contrasting the branch that uses stack storage with the branch that uses malloc. |
This version of the sort (which I derived from the first) has a more primitive "core" implementation, and a wrapper around that. The "core" requires that the user pass workspace to it (much as Fortran 77 procedures often do). The wrapper uses stack storage for the workspaces, if the sorted subarray is small; otherwise it uses malloc. One may be interested in contrasting the branch that uses stack storage with the branch that uses malloc. |
||
< |
<syntaxhighlight lang="ats">(* A version of the patience sort that uses arrays passed to it as its |
||
workspace, and returns the results in an array passed to it. |
workspace, and returns the results in an array passed to it. |
||
Line 2,698: | Line 2,698: | ||
end |
end |
||
(*------------------------------------------------------------------*)</ |
(*------------------------------------------------------------------*)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,711: | Line 2,711: | ||
The mergesort proves the result has the same length as the original, but this patience sort does not. |
The mergesort proves the result has the same length as the original, but this patience sort does not. |
||
< |
<syntaxhighlight lang="ats">//-------------------------------------------------------------------- |
||
// |
// |
||
// A patience sort for 32-bit signed integers. |
// A patience sort for 32-bit signed integers. |
||
Line 3,082: | Line 3,082: | ||
end |
end |
||
(*------------------------------------------------------------------*)</ |
(*------------------------------------------------------------------*)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,090: | Line 3,090: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">PatienceSort(A){ |
||
P:=0, Pile:=[], Result:=[] |
P:=0, Pile:=[], Result:=[] |
||
for k, v in A |
for k, v in A |
||
Line 3,149: | Line 3,149: | ||
} |
} |
||
return Result |
return Result |
||
}</ |
}</syntaxhighlight> |
||
Examples:< |
Examples:<syntaxhighlight lang="autohotkey">Test := [[4, 65, 2, -31, 0, 99, 83, 782, 1] |
||
,["n", "o", "n", "z", "e", "r", "o", "s", "u", "m"] |
,["n", "o", "n", "z", "e", "r", "o", "s", "u", "m"] |
||
,["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"]] |
,["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"]] |
||
Line 3,161: | Line 3,161: | ||
MsgBox % "[" Trim(output, ", ") "]" |
MsgBox % "[" Trim(output, ", ") "]" |
||
} |
} |
||
return</ |
return</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Pile1 = [-31, 2, 4] |
<pre>Pile1 = [-31, 2, 4] |
||
Line 3,184: | Line 3,184: | ||
=={{header|C}}== |
=={{header|C}}== |
||
Takes integers as input, prints out usage on incorrect invocation |
Takes integers as input, prints out usage on incorrect invocation |
||
<syntaxhighlight lang="c"> |
|||
<lang C> |
|||
#include<stdlib.h> |
#include<stdlib.h> |
||
#include<stdio.h> |
#include<stdio.h> |
||
Line 3,250: | Line 3,250: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Invocation and output : |
Invocation and output : |
||
<pre> |
<pre> |
||
Line 3,258: | Line 3,258: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp">#include <iostream> |
||
#include <vector> |
#include <vector> |
||
#include <stack> |
#include <stack> |
||
Line 3,321: | Line 3,321: | ||
std::cout << std::endl; |
std::cout << std::endl; |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>-31, 0, 1, 2, 4, 65, 83, 99, 782, </pre> |
<pre>-31, 0, 1, 2, 4, 65, 83, 99, 782, </pre> |
||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
< |
<syntaxhighlight lang="clojure"> |
||
(defn patience-insert |
(defn patience-insert |
||
"Inserts a value into the sequence where each element is a stack. |
"Inserts a value into the sequence where each element is a stack. |
||
Line 3,392: | Line 3,392: | ||
;; Sort the test sequence and print it |
;; Sort the test sequence and print it |
||
(println (patience-sort [4 65 2 -31 0 99 83 782 1])) |
(println (patience-sort [4 65 2 -31 0 99 83 782 1])) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>[-31 0 1 2 4 65 83 99 782]</pre> |
<pre>[-31 0 1 2 4 65 83 99 782]</pre> |
||
Line 3,398: | Line 3,398: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.array, std.range, std.algorithm; |
||
void patienceSort(T)(T[] items) /*pure nothrow @safe*/ |
void patienceSort(T)(T[] items) /*pure nothrow @safe*/ |
||
Line 3,426: | Line 3,426: | ||
assert(data.isSorted); |
assert(data.isSorted); |
||
data.writeln; |
data.writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[-31, 0, 1, 2, 4, 65, 83, 99, 782]</pre> |
<pre>[-31, 0, 1, 2, 4, 65, 83, 99, 782]</pre> |
||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
< |
<syntaxhighlight lang="elixir">defmodule Sort do |
||
def patience_sort(list) do |
def patience_sort(list) do |
||
piles = deal_pile(list, []) |
piles = deal_pile(list, []) |
||
Line 3,465: | Line 3,465: | ||
end |
end |
||
IO.inspect Sort.patience_sort [4, 65, 2, -31, 0, 99, 83, 782, 1]</ |
IO.inspect Sort.patience_sort [4, 65, 2, -31, 0, 99, 83, 782, 1]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,486: | Line 3,486: | ||
< |
<syntaxhighlight lang="fortran">module rosetta_code_patience_sort |
||
implicit none |
implicit none |
||
private |
private |
||
Line 3,781: | Line 3,781: | ||
end function less |
end function less |
||
end program patience_sort_task</ |
end program patience_sort_task</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,790: | Line 3,790: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
This version is written for int slices, but can be easily modified to sort other types. |
This version is written for int slices, but can be easily modified to sort other types. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 3,848: | Line 3,848: | ||
patience_sort(a) |
patience_sort(a) |
||
fmt.Println(a) |
fmt.Println(a) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[-31 0 1 2 4 65 83 99 782]</pre> |
<pre>[-31 0 1 2 4 65 83 99 782]</pre> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import Control.Monad.ST |
||
import Control.Monad |
import Control.Monad |
||
import Data.Array.ST |
import Data.Array.ST |
||
Line 3,900: | Line 3,900: | ||
main :: IO () |
main :: IO () |
||
main = print $ patienceSort [4, 65, 2, -31, 0, 99, 83, 782, 1]</ |
main = print $ patienceSort [4, 65, 2, -31, 0, 99, 83, 782, 1]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[-31,0,1,2,4,65,83,99,782]</pre> |
<pre>[-31,0,1,2,4,65,83,99,782]</pre> |
||
Line 3,908: | Line 3,908: | ||
< |
<syntaxhighlight lang="icon">#--------------------------------------------------------------------- |
||
# |
# |
||
# Patience sorting. |
# Patience sorting. |
||
Line 4,142: | Line 4,142: | ||
end |
end |
||
#---------------------------------------------------------------------</ |
#---------------------------------------------------------------------</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,151: | Line 4,151: | ||
=={{header|J}}== |
=={{header|J}}== |
||
The data structure for append and transfer are as x argument a list with [[wp:CAR_and_CDR|cdr]] as the stacks and [[wp:CAR_and_CDR|car]] as the data to sort or growing sorted list; and the y argument being the index of pile to operate on. New piles are created by using the new value, accomplished by selecting the entire x argument as a result. Filtering removes empty stacks during unpiling. |
The data structure for append and transfer are as x argument a list with [[wp:CAR_and_CDR|cdr]] as the stacks and [[wp:CAR_and_CDR|car]] as the data to sort or growing sorted list; and the y argument being the index of pile to operate on. New piles are created by using the new value, accomplished by selecting the entire x argument as a result. Filtering removes empty stacks during unpiling. |
||
<syntaxhighlight lang="j"> |
|||
<lang J> |
|||
Until =: 2 :'u^:(0=v)^:_' |
Until =: 2 :'u^:(0=v)^:_' |
||
Filter =: (#~`)(`:6) |
Filter =: (#~`)(`:6) |
||
Line 4,178: | Line 4,178: | ||
unpile_demo =: >@:{.@:((0<#S:0)Filter@:(transfer Show smallest)Until(1=#))@:(a:&,) |
unpile_demo =: >@:{.@:((0<#S:0)Filter@:(transfer Show smallest)Until(1=#))@:(a:&,) |
||
patience_sort_demo =: unpile_demo@:pile_demo |
patience_sort_demo =: unpile_demo@:pile_demo |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre> |
<pre> |
||
Line 4,289: | Line 4,289: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang="java">import java.util.*; |
||
public class PatienceSort { |
public class PatienceSort { |
||
Line 4,326: | Line 4,326: | ||
System.out.println(Arrays.toString(a)); |
System.out.println(Arrays.toString(a)); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[-31, 0, 1, 2, 4, 65, 83, 99, 782]</pre> |
<pre>[-31, 0, 1, 2, 4, 65, 83, 99, 782]</pre> |
||
=={{header|Javascript}}== |
=={{header|Javascript}}== |
||
< |
<syntaxhighlight lang="javascript">const patienceSort = (nums) => { |
||
const piles = [] |
const piles = [] |
||
Line 4,364: | Line 4,364: | ||
} |
} |
||
console.log(patienceSort([10,6,-30,9,18,1,-20])); |
console.log(patienceSort([10,6,-30,9,18,1,-20])); |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>[-30, -20, 1, 6, 9, 10, 18]</pre> |
<pre>[-30, -20, 1, 6, 9, 10, 18]</pre> |
||
Line 4,372: | Line 4,372: | ||
{{works with|jq}} |
{{works with|jq}} |
||
'''Works with gojq, the Go implementation of jq''' |
'''Works with gojq, the Go implementation of jq''' |
||
< |
<syntaxhighlight lang="jq">def patienceSort: |
||
length as $size |
length as $size |
||
| if $size < 2 then . |
| if $size < 2 then . |
||
Line 4,407: | Line 4,407: | ||
["n", "o", "n", "z", "e", "r", "o", "s", "u", "m"], |
["n", "o", "n", "z", "e", "r", "o", "s", "u", "m"], |
||
["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"] |
["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"] |
||
| patienceSort</ |
| patienceSort</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,416: | Line 4,416: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">function patiencesort(list::Vector{T}) where T |
||
piles = Vector{Vector{T}}() |
piles = Vector{Vector{T}}() |
||
for n in list |
for n in list |
||
Line 4,444: | Line 4,444: | ||
println(patiencesort(rand(collect(1:1000), 12))) |
println(patiencesort(rand(collect(1:1000), 12))) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
[186, 243, 255, 257, 427, 486, 513, 613, 657, 734, 866, 907] |
[186, 243, 255, 257, 427, 486, 513, 613, 657, 734, 866, 907] |
||
Line 4,450: | Line 4,450: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.1.2 |
||
fun <T : Comparable<T>> patienceSort(arr: Array<T>) { |
fun <T : Comparable<T>> patienceSort(arr: Array<T>) { |
||
Line 4,491: | Line 4,491: | ||
patienceSort(sArr) |
patienceSort(sArr) |
||
println(sArr.contentToString()) |
println(sArr.contentToString()) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,508: | Line 4,508: | ||
< |
<syntaxhighlight lang="mercury">:- module patience_sort_task. |
||
:- interface. |
:- interface. |
||
Line 4,871: | Line 4,871: | ||
%%% mode: mercury |
%%% mode: mercury |
||
%%% prolog-indent-width: 2 |
%%% prolog-indent-width: 2 |
||
%%% end:</ |
%%% end:</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,888: | Line 4,888: | ||
Unlike the Ada upon which it is based, this implementation of patience sort is specific to arrays of integers, rather than generic. |
Unlike the Ada upon which it is based, this implementation of patience sort is specific to arrays of integers, rather than generic. |
||
< |
<syntaxhighlight lang="modula2">MODULE PatienceSortTask; |
||
FROM STextIO IMPORT WriteString; |
FROM STextIO IMPORT WriteString; |
||
Line 5,167: | Line 5,167: | ||
END; |
END; |
||
WriteLn; |
WriteLn; |
||
END PatienceSortTask.</ |
END PatienceSortTask.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,175: | Line 5,175: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">import std/decls |
||
func patienceSort[T](a: var openArray[T]) = |
func patienceSort[T](a: var openArray[T]) = |
||
Line 5,215: | Line 5,215: | ||
var sArray = ["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"] |
var sArray = ["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"] |
||
sArray.patienceSort() |
sArray.patienceSort() |
||
echo sArray</ |
echo sArray</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,223: | Line 5,223: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
< |
<syntaxhighlight lang="ocaml">module PatienceSortFn (Ord : Set.OrderedType) : sig |
||
val patience_sort : Ord.t list -> Ord.t list |
val patience_sort : Ord.t list -> Ord.t list |
||
end = struct |
end = struct |
||
Line 5,273: | Line 5,273: | ||
let patience_sort n = |
let patience_sort n = |
||
merge_piles (sort_into_piles n) |
merge_piles (sort_into_piles n) |
||
end</ |
end</syntaxhighlight> |
||
Usage: |
Usage: |
||
<pre># module IntPatienceSort = PatienceSortFn |
<pre># module IntPatienceSort = PatienceSortFn |
||
Line 5,288: | Line 5,288: | ||
{{works with|Free Pascal Compiler|3.2.2}} |
{{works with|Free Pascal Compiler|3.2.2}} |
||
< |
<syntaxhighlight lang="pascal">PatienceSortTask (Output); |
||
CONST MaxSortSize = 1024; { A power of two. } |
CONST MaxSortSize = 1024; { A power of two. } |
||
Line 5,565: | Line 5,565: | ||
END; |
END; |
||
WriteLn |
WriteLn |
||
END.</ |
END.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,580: | Line 5,580: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="perl">sub patience_sort { |
||
my @s = [shift]; |
my @s = [shift]; |
||
for my $card (@_) { |
for my $card (@_) { |
||
Line 5,600: | Line 5,600: | ||
print join ' ', patience_sort qw(4 3 6 2 -1 13 12 9); |
print join ' ', patience_sort qw(4 3 6 2 -1 13 12 9); |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>-1 2 3 4 6 9 12 13</pre> |
<pre>-1 2 3 4 6 9 12 13</pre> |
||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
Line 5,644: | Line 5,644: | ||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">patience_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]),{</span><span style="color: #004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">})</span> |
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">patience_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]),{</span><span style="color: #004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">})</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 5,654: | Line 5,654: | ||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
< |
<syntaxhighlight lang="php"><?php |
||
class PilesHeap extends SplMinHeap { |
class PilesHeap extends SplMinHeap { |
||
public function compare($pile1, $pile2) { |
public function compare($pile1, $pile2) { |
||
Line 5,696: | Line 5,696: | ||
patience_sort($a); |
patience_sort($a); |
||
print_r($a); |
print_r($a); |
||
?></ |
?></syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Array |
<pre>Array |
||
Line 5,712: | Line 5,712: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(de leftmost (Lst N H) |
||
(let L 1 |
(let L 1 |
||
(while (<= L H) |
(while (<= L H) |
||
Line 5,745: | Line 5,745: | ||
(patience (4 65 2 -31 0 99 83 782 1)) ) |
(patience (4 65 2 -31 0 99 83 782 1)) ) |
||
(bye)</ |
(bye)</syntaxhighlight> |
||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
< |
<syntaxhighlight lang="prolog">patience_sort(UnSorted,Sorted) :- |
||
make_piles(UnSorted,[],Piled), |
make_piles(UnSorted,[],Piled), |
||
merge_piles(Piled,[],Sorted). |
merge_piles(Piled,[],Sorted). |
||
Line 5,776: | Line 5,776: | ||
merge_pile([N|T1],[P|T2],[N|R]) :- |
merge_pile([N|T1],[P|T2],[N|R]) :- |
||
N < P, |
N < P, |
||
merge_pile(T1,[P|T2],R).</ |
merge_pile(T1,[P|T2],R).</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 5,785: | Line 5,785: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
{{works with|Python|2.7+ and 3.2+}} (for <tt>functools.total_ordering</tt>) |
{{works with|Python|2.7+ and 3.2+}} (for <tt>functools.total_ordering</tt>) |
||
< |
<syntaxhighlight lang="python">from functools import total_ordering |
||
from bisect import bisect_left |
from bisect import bisect_left |
||
from heapq import merge |
from heapq import merge |
||
Line 5,811: | Line 5,811: | ||
a = [4, 65, 2, -31, 0, 99, 83, 782, 1] |
a = [4, 65, 2, -31, 0, 99, 83, 782, 1] |
||
patience_sort(a) |
patience_sort(a) |
||
print a</ |
print a</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[-31, 0, 1, 2, 4, 65, 83, 99, 782]</pre> |
<pre>[-31, 0, 1, 2, 4, 65, 83, 99, 782]</pre> |
||
Line 5,819: | Line 5,819: | ||
uses <code>bsearchwith</code> from [[Binary search#Quackery]] and <code>merge</code> from [[Merge sort#Quackery]]. |
uses <code>bsearchwith</code> from [[Binary search#Quackery]] and <code>merge</code> from [[Merge sort#Quackery]]. |
||
< |
<syntaxhighlight lang="quackery"> [ dip [ 0 over size rot ] |
||
nested bsearchwith |
nested bsearchwith |
||
[ -1 peek |
[ -1 peek |
||
Line 5,848: | Line 5,848: | ||
' [ 0 1 2 3 4 5 6 7 8 9 ] |
' [ 0 1 2 3 4 5 6 7 8 9 ] |
||
shuffle dup echo cr |
shuffle dup echo cr |
||
patience-sort echo</ |
patience-sort echo</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,857: | Line 5,857: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket">#lang racket/base |
||
(require racket/match racket/list) |
(require racket/match racket/list) |
||
Line 5,888: | Line 5,888: | ||
[((cons ush ust) least) (scan ush (cons least seens) ust)]))]))) |
[((cons ush ust) least) (scan ush (cons least seens) ust)]))]))) |
||
(patience-sort (shuffle (for/list ((_ 10)) (random 7))) <)</ |
(patience-sort (shuffle (for/list ((_ 10)) (random 7))) <)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>'(1 1 2 2 2 3 4 4 4 5)</pre> |
<pre>'(1 1 2 2 2 3 4 4 4 5)</pre> |
||
Line 5,895: | Line 5,895: | ||
(formerly Perl 6) |
(formerly Perl 6) |
||
{{works with|rakudo|2015-10-22}} |
{{works with|rakudo|2015-10-22}} |
||
<lang |
<syntaxhighlight lang="raku" line>multi patience(*@deck) { |
||
my @stacks; |
my @stacks; |
||
for @deck -> $card { |
for @deck -> $card { |
||
Line 5,911: | Line 5,911: | ||
} |
} |
||
say ~patience ^10 . pick(*);</ |
say ~patience ^10 . pick(*);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>0 1 2 3 4 5 6 7 8 9</pre> |
<pre>0 1 2 3 4 5 6 7 8 9</pre> |
||
Line 5,919: | Line 5,919: | ||
Duplicates are also sorted correctly. |
Duplicates are also sorted correctly. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program sorts a list of things (or items) using the patience sort algorithm. */ |
||
parse arg xxx; say ' input: ' xxx /*obtain a list of things from the C.L.*/ |
parse arg xxx; say ' input: ' xxx /*obtain a list of things from the C.L.*/ |
||
n= words(xxx); #= 0; !.= 1 /*N: # of things; #: number of piles*/ |
n= words(xxx); #= 0; !.= 1 /*N: # of things; #: number of piles*/ |
||
Line 5,943: | Line 5,943: | ||
end /*k*/ /* [↑] each iteration finds a low item*/ |
end /*k*/ /* [↑] each iteration finds a low item*/ |
||
/* [↓] string $ has a leading blank.*/ |
/* [↓] string $ has a leading blank.*/ |
||
say 'output: ' strip($) /*stick a fork in it, we're all done. */</ |
say 'output: ' strip($) /*stick a fork in it, we're all done. */</syntaxhighlight> |
||
{{out|output|text= when using the input of: <tt> 4 65 2 -31 0 99 83 782 7.88 1e1 1 </tt>}} |
{{out|output|text= when using the input of: <tt> 4 65 2 -31 0 99 83 782 7.88 1e1 1 </tt>}} |
||
<pre> |
<pre> |
||
Line 5,956: | Line 5,956: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">class Array |
||
def patience_sort |
def patience_sort |
||
piles = [] |
piles = [] |
||
Line 5,979: | Line 5,979: | ||
a = [4, 65, 2, -31, 0, 99, 83, 782, 1] |
a = [4, 65, 2, -31, 0, 99, 83, 782, 1] |
||
p a.patience_sort</ |
p a.patience_sort</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,988: | Line 5,988: | ||
{{libheader|Scala Time complexity O(n log n)}} |
{{libheader|Scala Time complexity O(n log n)}} |
||
{{works with|Scala|2.13}} |
{{works with|Scala|2.13}} |
||
< |
<syntaxhighlight lang="scala">import scala.collection.mutable |
||
object PatienceSort extends App { |
object PatienceSort extends App { |
||
Line 6,024: | Line 6,024: | ||
println(sort(List(4, 65, 2, -31, 0, 99, 83, 782, 1))) |
println(sort(List(4, 65, 2, -31, 0, 99, 83, 782, 1))) |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
Line 6,035: | Line 6,035: | ||
< |
<syntaxhighlight lang="scheme">(define-library (rosetta-code k-way-merge) |
||
(export k-way-merge) |
(export k-way-merge) |
||
Line 6,268: | Line 6,268: | ||
(newline) |
(newline) |
||
;;--------------------------------------------------------------------</ |
;;--------------------------------------------------------------------</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 6,276: | Line 6,276: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func patience(deck) { |
||
var stacks = []; |
var stacks = []; |
||
deck.each { |card| |
deck.each { |card| |
||
Line 6,298: | Line 6,298: | ||
var a = [4, 65, 2, -31, 0, 99, 83, 782, 1] |
var a = [4, 65, 2, -31, 0, 99, 83, 782, 1] |
||
say patience(a)</ |
say patience(a)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 6,306: | Line 6,306: | ||
=={{header|Standard ML}}== |
=={{header|Standard ML}}== |
||
{{works with|SML/NJ}} |
{{works with|SML/NJ}} |
||
< |
<syntaxhighlight lang="sml">structure PilePriority = struct |
||
type priority = int |
type priority = int |
||
fun compare (x, y) = Int.compare (y, x) (* we want min-heap *) |
fun compare (x, y) = Int.compare (y, x) (* we want min-heap *) |
||
Line 6,360: | Line 6,360: | ||
fun patience_sort n = |
fun patience_sort n = |
||
merge_piles (sort_into_piles n)</ |
merge_piles (sort_into_piles n)</syntaxhighlight> |
||
Usage: |
Usage: |
||
<pre>- patience_sort [4, 65, 2, ~31, 0, 99, 83, 782, 1]; |
<pre>- patience_sort [4, 65, 2, ~31, 0, 99, 83, 782, 1]; |
||
Line 6,368: | Line 6,368: | ||
{{works with|Tcl|8.6}} |
{{works with|Tcl|8.6}} |
||
This uses the <code>-bisect</code> option to <code>lsearch</code> in order to do an efficient binary search (in combination with <code>-index end</code>, which means that the search is indexed by the end of the sublist). |
This uses the <code>-bisect</code> option to <code>lsearch</code> in order to do an efficient binary search (in combination with <code>-index end</code>, which means that the search is indexed by the end of the sublist). |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.6 |
||
proc patienceSort {items} { |
proc patienceSort {items} { |
||
Line 6,401: | Line 6,401: | ||
} |
} |
||
return $result |
return $result |
||
}</ |
}</syntaxhighlight> |
||
Demonstrating: |
Demonstrating: |
||
< |
<syntaxhighlight lang="tcl">puts [patienceSort {4 65 2 -31 0 99 83 782 1}]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>-31 0 1 2 4 65 83 99 782</pre> |
<pre>-31 0 1 2 4 65 83 99 782</pre> |
||
Line 6,410: | Line 6,410: | ||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
{{libheader|Wren-sort}} |
{{libheader|Wren-sort}} |
||
< |
<syntaxhighlight lang="ecmascript">import "/sort" for Cmp |
||
var patienceSort = Fn.new { |a| |
var patienceSort = Fn.new { |a| |
||
Line 6,454: | Line 6,454: | ||
var sa = ["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"] |
var sa = ["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"] |
||
patienceSort.call(sa) |
patienceSort.call(sa) |
||
System.print(sa)</ |
System.print(sa)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 6,464: | Line 6,464: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
< |
<syntaxhighlight lang="zkl">fcn patienceSort(ns){ |
||
piles:=L(); |
piles:=L(); |
||
foreach n in (ns){ newPile:=True; // create list of sorted lists |
foreach n in (ns){ newPile:=True; // create list of sorted lists |
||
Line 6,480: | Line 6,480: | ||
} |
} |
||
r.close(); |
r.close(); |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">T(T(3,2,6,4,3,5,1), |
||
T(4,65,2,-31,0,99,83,782,1), |
T(4,65,2,-31,0,99,83,782,1), |
||
T(0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15), |
T(0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15), |
||
"foobar") |
"foobar") |
||
.pump(Console.println,patienceSort);</ |
.pump(Console.println,patienceSort);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |