Sorting algorithms/Patience sort: Difference between revisions

{{trans|Kotlin}}

 

I arr.len < 2 {R}

 

V sArr = [‘dog’, ‘cow’, ‘cat’, ‘ape’, ‘ant’, ‘man’, ‘pig’, ‘ass’, ‘gnu’]

patience_sort(&sArr)

 

{{out}}

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

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

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program patienceSort64.s */

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

.include "../includeARM64.inc"

 

=={{header|Ada}}==

 

 

 

with Ada.Text_IO;

end patience_sort_task;

 

 

{{out}}

 

=={{header|AppleScript}}==

on patienceSort(theList, l, r) -- Sort items l thru r of theList.

set listLen to (count theList)

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)

 

{{output}}

 

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

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program patienceSort.s */

/***************************************************/

.include "../affichage.inc"

 

=={{header|ATS}}==

The sort routine returns an array of indices into the original array, which is left unmodified.

 

 

#include "share/atspre_staload.hats"

end

 

 

{{out}}

<pre>$ patscc -O3 -DATS_MEMALLOC_LIBC patience_sort_task.dats && ./a.out

unsorted 22 15 98 82 22 4 58 70 80 38 49 48 46 54 93 8 54 2 72 84 86 76 53 37 90

sorted 2 4 8 15 22 22 37 38 46 48 49 53 54 54 58 70 72 76 80 82 84 86 90 93 98</pre>

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.

end

 

 

{{out}}

 

=={{header|AutoHotkey}}==

P:=0, Pile:=[], Result:=[]

for k, v in A

}

return Result

,["n", "o", "n", "z", "e", "r", "o", "s", "u", "m"]

,["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"]]

MsgBox % "[" Trim(output, ", ") "]"

}

{{out}}

<pre>Pile1 = [-31, 2, 4]

=={{header|C}}==

Takes integers as input, prints out usage on incorrect invocation

#include<stdlib.h>

#include<stdio.h>

return 0;

}

Invocation and output :

<pre>

 

=={{header|C++}}==

#include <vector>

#include <stack>

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.

;; Sort the test sequence and print it

(println (patience-sort [4 65 2 -31 0 99 83 782 1]))

{{out}}

<pre>[-31 0 1 2 4 65 83 99 782]</pre>

=={{header|D}}==

{{trans|Python}}

 

void patienceSort(T)(T[] items) /*pure nothrow @safe*/

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, [])

end

 

 

{{out}}

 

 

implicit none

private

end function less

 

 

{{out}}

=={{header|Go}}==

This version is written for int slices, but can be easily modified to sort other types.

 

import (

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

 

main :: IO ()

{{out}}

<pre>[-31,0,1,2,4,65,83,99,782]</pre>

 

 

#

# Patience sorting.

end

 

 

{{out}}

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

Until =: 2 :'u^:(0=v)^:_'

Filter =: (#~`)(`:6)

unpile_demo =: >@:{.@:((0<#S:0)Filter@:(transfer Show smallest)Until(1=#))@:(a:&,)

patience_sort_demo =: unpile_demo@:pile_demo

 

<pre>

 

=={{header|Java}}==

 

public class PatienceSort {

System.out.println(Arrays.toString(a));

}

{{out}}

<pre>[-31, 0, 1, 2, 4, 65, 83, 99, 782]</pre>

 

=={{header|Javascript}}==

const piles = []

 

}

console.log(patienceSort([10,6,-30,9,18,1,-20]));

{{out}}

<pre>[-30, -20, 1, 6, 9, 10, 18]</pre>

{{works with|jq}}

'''Works with gojq, the Go implementation of jq'''

length as $size

| if $size < 2 then .

["n", "o", "n", "z", "e", "r", "o", "s", "u", "m"],

["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"]

{{out}}

<pre>

 

=={{header|Julia}}==

piles = Vector{Vector{T}}()

for n in list

println(patiencesort(rand(collect(1:1000), 12)))

<pre>

[186, 243, 255, 257, 427, 486, 513, 613, 657, 734, 866, 907]

 

=={{header|Kotlin}}==

 

fun <T : Comparable<T>> patienceSort(arr: Array<T>) {

patienceSort(sArr)

println(sArr.contentToString())

 

{{out}}

 

 

 

:- interface.

%%% mode: mercury

%%% prolog-indent-width: 2

 

{{out}}

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;

END;

WriteLn;

 

{{out}}

 

=={{header|Nim}}==

 

func patienceSort[T](a: var openArray[T]) =

var sArray = ["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"]

sArray.patienceSort()

 

{{out}}

 

=={{header|OCaml}}==

val patience_sort : Ord.t list -> Ord.t list

end = struct

let patience_sort n =

merge_piles (sort_into_piles n)

Usage:

<pre># module IntPatienceSort = PatienceSortFn

{{works with|Free Pascal Compiler|3.2.2}}

 

 

CONST MaxSortSize = 1024; { A power of two. }

END;

WriteLn

 

{{out}}

=={{header|Perl}}==

{{trans|Raku}}

my @s = [shift];

for my $card (@_) {

 

print join ' ', patience_sort qw(4 3 6 2 -1 13 12 9);

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

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

 

=={{header|PHP}}==

class PilesHeap extends SplMinHeap {

public function compare($pile1, $pile2) {

patience_sort($a);

print_r($a);

{{out}}

<pre>Array

 

=={{header|PicoLisp}}==

(let L 1

(while (<= L H)

(patience (4 65 2 -31 0 99 83 782 1)) )

 

=={{header|Prolog}}==

make_piles(UnSorted,[],Piled),

merge_piles(Piled,[],Sorted).

merge_pile([N|T1],[P|T2],[N|R]) :-

N < P,

{{out}}

<pre>

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

a = [4, 65, 2, -31, 0, 99, 83, 782, 1]

patience_sort(a)

{{out}}

<pre>[-31, 0, 1, 2, 4, 65, 83, 99, 782]</pre>

uses <code>bsearchwith</code> from [[Binary search#Quackery]] and <code>merge</code> from [[Merge sort#Quackery]].

 

nested bsearchwith

[ -1 peek

' [ 0 1 2 3 4 5 6 7 8 9 ]

shuffle dup echo cr

 

{{out}}

=={{header|Racket}}==

 

(require racket/match racket/list)

 

[((cons ush ust) least) (scan ush (cons least seens) ust)]))])))

 

{{out}}

<pre>'(1 1 2 2 2 3 4 4 4 5)</pre>

(formerly Perl 6)

{{works with|rakudo|2015-10-22}}

my @stacks;

for @deck -> $card {

}

 

{{out}}

<pre>0 1 2 3 4 5 6 7 8 9</pre>

 

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

end /*k*/ /* [↑] each iteration finds a low item*/

/* [↓] string $ has a leading blank.*/

{{out|output|text=&nbsp; when using the input of: &nbsp; <tt> 4 65 2 -31 0 99 83 782 7.88 1e1 1 </tt>}}

<pre>

 

=={{header|Ruby}}==

def patience_sort

piles = []

 

a = [4, 65, 2, -31, 0, 99, 83, 782, 1]

 

{{out}}

{{libheader|Scala Time complexity O(n log n)}}

{{works with|Scala|2.13}}

 

object PatienceSort extends App {

 

println(sort(List(4, 65, 2, -31, 0, 99, 83, 782, 1)))

 

=={{header|Scheme}}==

 

 

 

(export k-way-merge)

(newline)

 

 

{{out}}

 

=={{header|Sidef}}==

var stacks = [];

deck.each { |card|

 

var a = [4, 65, 2, -31, 0, 99, 83, 782, 1]

{{out}}

<pre>

=={{header|Standard ML}}==

{{works with|SML/NJ}}

type priority = int

fun compare (x, y) = Int.compare (y, x) (* we want min-heap *)

 

fun patience_sort n =

Usage:

<pre>- patience_sort [4, 65, 2, ~31, 0, 99, 83, 782, 1];

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

}

return $result

Demonstrating:

{{out}}

<pre>-31 0 1 2 4 65 83 99 782</pre>

{{trans|Kotlin}}

{{libheader|Wren-sort}}

 

var patienceSort = Fn.new { |a|

var sa = ["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"]

patienceSort.call(sa)

 

{{out}}

 

=={{header|zkl}}==

piles:=L();

foreach n in (ns){ newPile:=True; // create list of sorted lists

}

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

{{out}}

<pre>