
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort


Sort an array of numbers (of any convenient size) into ascending order using   Patience sorting.



Related task

   Longest increasing subsequence


import "/sort" for Cmp
 
var patienceSort = Fn.new { |a|
    var size = a.count
    if (size < 2) return
    var cmp = Cmp.default(a[0])
    var piles = []
    for (e in a) {
        var outer = false
        for (pile in piles) {
            if (cmp.call(pile[-1], e) > 0) {
                pile.add(e)
                outer = true
                break
            }
        }
        if (!outer) piles.add([e])
    }
    for (i in 0...size) {
        var min = piles[0][-1]
        var minPileIndex = 0
        for (j in 1...piles.count) {
            if (cmp.call(piles[j][-1], min) < 0) {
                min = piles[j][-1]
                minPileIndex = j
            }
        }
        a[i] = min
        var minPile = piles[minPileIndex]
        minPile.removeAt(-1)
        if (minPile.count == 0) piles.removeAt(minPileIndex)
    }
}
 
var ia = [4, 65, 2, -31, 0, 99, 83, 782, 1]
patienceSort.call(ia)
System.print(ia)
 
var ca = ["n", "o", "n", "z", "e", "r", "o", "s", "u", "m"]
patienceSort.call(ca)
System.print(ca)
 
var sa = ["dog", "cow", "cat", "ape", "ant", "man", "pig", "ass", "gnu"]
patienceSort.call(sa)
System.print(sa)