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

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.

end

{{out}}

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>