Sorting algorithms/Patience sort: Difference between revisions
m
syntax highlighting fixup automation
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 13:
{{trans|Kotlin}}
<
I arr.len < 2 {R}
Line 48:
V sArr = [‘dog’, ‘cow’, ‘cat’, ‘ape’, ‘ant’, ‘man’, ‘pig’, ‘ass’, ‘gnu’]
patience_sort(&sArr)
print(sArr)</
{{out}}
Line 59:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program patienceSort64.s */
Line 422:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|Ada}}==
Line 432:
<
with Ada.Text_IO;
Line 719:
end patience_sort_task;
----------------------------------------------------------------------</
{{out}}
Line 727:
=={{header|AppleScript}}==
<
on patienceSort(theList, l, r) -- Sort items l thru r of theList.
set listLen to (count theList)
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}
sort(aList, 1, -1)
return aList</
{{output}}
<
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program patienceSort.s */
Line 1,121:
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
=={{header|ATS}}==
Line 1,131:
The sort routine returns an array of indices into the original array, which is left unmodified.
<
#include "share/atspre_staload.hats"
Line 1,810:
end
(*------------------------------------------------------------------*)</
{{out}}
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.
<
workspace, and returns the results in an array passed to it.
Line 2,698:
end
(*------------------------------------------------------------------*)</
{{out}}
Line 2,711:
The mergesort proves the result has the same length as the original, but this patience sort does not.
<
//
// A patience sort for 32-bit signed integers.
Line 3,082:
end
(*------------------------------------------------------------------*)</
{{out}}
Line 3,090:
=={{header|AutoHotkey}}==
<
P:=0, Pile:=[], Result:=[]
for k, v in A
Line 3,149:
}
return Result
}</
Examples:<
,["n", "o", "n", "z", "e", "r", "o", "s", "u", "m"]
,["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"]]
Line 3,161:
MsgBox % "[" Trim(output, ", ") "]"
}
return</
{{out}}
<pre>Pile1 = [-31, 2, 4]
Line 3,184:
=={{header|C}}==
Takes integers as input, prints out usage on incorrect invocation
<syntaxhighlight lang="c">
#include<stdlib.h>
#include<stdio.h>
Line 3,250:
return 0;
}
</syntaxhighlight>
Invocation and output :
<pre>
Line 3,258:
=={{header|C++}}==
<
#include <vector>
#include <stack>
Line 3,321:
std::cout << std::endl;
return 0;
}</
{{out}}
<pre>-31, 0, 1, 2, 4, 65, 83, 99, 782, </pre>
=={{header|Clojure}}==
<
(defn patience-insert
"Inserts a value into the sequence where each element is a stack.
Line 3,392:
;; Sort the test sequence and print it
(println (patience-sort [4 65 2 -31 0 99 83 782 1]))
</syntaxhighlight>
{{out}}
<pre>[-31 0 1 2 4 65 83 99 782]</pre>
Line 3,398:
=={{header|D}}==
{{trans|Python}}
<
void patienceSort(T)(T[] items) /*pure nothrow @safe*/
Line 3,426:
assert(data.isSorted);
data.writeln;
}</
{{out}}
<pre>[-31, 0, 1, 2, 4, 65, 83, 99, 782]</pre>
=={{header|Elixir}}==
<
def patience_sort(list) do
piles = deal_pile(list, [])
Line 3,465:
end
IO.inspect Sort.patience_sort [4, 65, 2, -31, 0, 99, 83, 782, 1]</
{{out}}
Line 3,486:
<
implicit none
private
Line 3,781:
end function less
end program patience_sort_task</
{{out}}
Line 3,790:
=={{header|Go}}==
This version is written for int slices, but can be easily modified to sort other types.
<
import (
Line 3,848:
patience_sort(a)
fmt.Println(a)
}</
{{out}}
<pre>[-31 0 1 2 4 65 83 99 782]</pre>
=={{header|Haskell}}==
<
import Control.Monad
import Data.Array.ST
Line 3,900:
main :: IO ()
main = print $ patienceSort [4, 65, 2, -31, 0, 99, 83, 782, 1]</
{{out}}
<pre>[-31,0,1,2,4,65,83,99,782]</pre>
Line 3,908:
<
#
# Patience sorting.
Line 4,142:
end
#---------------------------------------------------------------------</
{{out}}
Line 4,151:
=={{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.
<syntaxhighlight lang="j">
Until =: 2 :'u^:(0=v)^:_'
Filter =: (#~`)(`:6)
Line 4,178:
unpile_demo =: >@:{.@:((0<#S:0)Filter@:(transfer Show smallest)Until(1=#))@:(a:&,)
patience_sort_demo =: unpile_demo@:pile_demo
</syntaxhighlight>
<pre>
Line 4,289:
=={{header|Java}}==
<
public class PatienceSort {
Line 4,326:
System.out.println(Arrays.toString(a));
}
}</
{{out}}
<pre>[-31, 0, 1, 2, 4, 65, 83, 99, 782]</pre>
=={{header|Javascript}}==
<
const piles = []
Line 4,364:
}
console.log(patienceSort([10,6,-30,9,18,1,-20]));
</syntaxhighlight>
{{out}}
<pre>[-30, -20, 1, 6, 9, 10, 18]</pre>
Line 4,372:
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<
length as $size
| if $size < 2 then .
Line 4,407:
["n", "o", "n", "z", "e", "r", "o", "s", "u", "m"],
["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"]
| patienceSort</
{{out}}
<pre>
Line 4,416:
=={{header|Julia}}==
<
piles = Vector{Vector{T}}()
for n in list
Line 4,444:
println(patiencesort(rand(collect(1:1000), 12)))
</
<pre>
[186, 243, 255, 257, 427, 486, 513, 613, 657, 734, 866, 907]
Line 4,450:
=={{header|Kotlin}}==
<
fun <T : Comparable<T>> patienceSort(arr: Array<T>) {
Line 4,491:
patienceSort(sArr)
println(sArr.contentToString())
}</
{{out}}
Line 4,508:
<
:- interface.
Line 4,871:
%%% mode: mercury
%%% prolog-indent-width: 2
%%% end:</
{{out}}
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.
<
FROM STextIO IMPORT WriteString;
Line 5,167:
END;
WriteLn;
END PatienceSortTask.</
{{out}}
Line 5,175:
=={{header|Nim}}==
<
func patienceSort[T](a: var openArray[T]) =
Line 5,215:
var sArray = ["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"]
sArray.patienceSort()
echo sArray</
{{out}}
Line 5,223:
=={{header|OCaml}}==
<
val patience_sort : Ord.t list -> Ord.t list
end = struct
Line 5,273:
let patience_sort n =
merge_piles (sort_into_piles n)
end</
Usage:
<pre># module IntPatienceSort = PatienceSortFn
Line 5,288:
{{works with|Free Pascal Compiler|3.2.2}}
<
CONST MaxSortSize = 1024; { A power of two. }
Line 5,565:
END;
WriteLn
END.</
{{out}}
Line 5,580:
=={{header|Perl}}==
{{trans|Raku}}
<
my @s = [shift];
for my $card (@_) {
Line 5,600:
print join ' ', patience_sort qw(4 3 6 2 -1 13 12 9);
</syntaxhighlight>
{{out}}
<pre>-1 2 3 4 6 9 12 13</pre>
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
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: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
<pre>
Line 5,654:
=={{header|PHP}}==
<
class PilesHeap extends SplMinHeap {
public function compare($pile1, $pile2) {
Line 5,696:
patience_sort($a);
print_r($a);
?></
{{out}}
<pre>Array
Line 5,712:
=={{header|PicoLisp}}==
<
(let L 1
(while (<= L H)
Line 5,745:
(patience (4 65 2 -31 0 99 83 782 1)) )
(bye)</
=={{header|Prolog}}==
<
make_piles(UnSorted,[],Piled),
merge_piles(Piled,[],Sorted).
Line 5,776:
merge_pile([N|T1],[P|T2],[N|R]) :-
N < P,
merge_pile(T1,[P|T2],R).</
{{out}}
<pre>
Line 5,785:
=={{header|Python}}==
{{works with|Python|2.7+ and 3.2+}} (for <tt>functools.total_ordering</tt>)
<
from bisect import bisect_left
from heapq import merge
Line 5,811:
a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
patience_sort(a)
print a</
{{out}}
<pre>[-31, 0, 1, 2, 4, 65, 83, 99, 782]</pre>
Line 5,819:
uses <code>bsearchwith</code> from [[Binary search#Quackery]] and <code>merge</code> from [[Merge sort#Quackery]].
<
nested bsearchwith
[ -1 peek
Line 5,848:
' [ 0 1 2 3 4 5 6 7 8 9 ]
shuffle dup echo cr
patience-sort echo</
{{out}}
Line 5,857:
=={{header|Racket}}==
<
(require racket/match racket/list)
Line 5,888:
[((cons ush ust) least) (scan ush (cons least seens) ust)]))])))
(patience-sort (shuffle (for/list ((_ 10)) (random 7))) <)</
{{out}}
<pre>'(1 1 2 2 2 3 4 4 4 5)</pre>
Line 5,895:
(formerly Perl 6)
{{works with|rakudo|2015-10-22}}
<syntaxhighlight lang="raku"
my @stacks;
for @deck -> $card {
Line 5,911:
}
say ~patience ^10 . pick(*);</
{{out}}
<pre>0 1 2 3 4 5 6 7 8 9</pre>
Line 5,919:
Duplicates are also sorted correctly.
<
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*/
Line 5,943:
end /*k*/ /* [↑] each iteration finds a low item*/
/* [↓] string $ has a leading blank.*/
say 'output: ' strip($) /*stick a fork in it, we're all done. */</
{{out|output|text= when using the input of: <tt> 4 65 2 -31 0 99 83 782 7.88 1e1 1 </tt>}}
<pre>
Line 5,956:
=={{header|Ruby}}==
<
def patience_sort
piles = []
Line 5,979:
a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
p a.patience_sort</
{{out}}
Line 5,988:
{{libheader|Scala Time complexity O(n log n)}}
{{works with|Scala|2.13}}
<
object PatienceSort extends App {
Line 6,024:
println(sort(List(4, 65, 2, -31, 0, 99, 83, 782, 1)))
}</
=={{header|Scheme}}==
Line 6,035:
<
(export k-way-merge)
Line 6,268:
(newline)
;;--------------------------------------------------------------------</
{{out}}
Line 6,276:
=={{header|Sidef}}==
<
var stacks = [];
deck.each { |card|
Line 6,298:
var a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
say patience(a)</
{{out}}
<pre>
Line 6,306:
=={{header|Standard ML}}==
{{works with|SML/NJ}}
<
type priority = int
fun compare (x, y) = Int.compare (y, x) (* we want min-heap *)
Line 6,360:
fun patience_sort n =
merge_piles (sort_into_piles n)</
Usage:
<pre>- patience_sort [4, 65, 2, ~31, 0, 99, 83, 782, 1];
Line 6,368:
{{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).
<
proc patienceSort {items} {
Line 6,401:
}
return $result
}</
Demonstrating:
<
{{out}}
<pre>-31 0 1 2 4 65 83 99 782</pre>
Line 6,410:
{{trans|Kotlin}}
{{libheader|Wren-sort}}
<
var patienceSort = Fn.new { |a|
Line 6,454:
var sa = ["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"]
patienceSort.call(sa)
System.print(sa)</
{{out}}
Line 6,464:
=={{header|zkl}}==
<
piles:=L();
foreach n in (ns){ newPile:=True; // create list of sorted lists
Line 6,480:
}
r.close();
}</
<
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),
"foobar")
.pump(Console.println,patienceSort);</
{{out}}
<pre>
|