Patience Sorting
August 22, 2014
This sorting algorithm derives its name from the game of Patience (that’s the British name, we call it Solitaire in the United States) because it is implemented by analogy to sorting a shuffled deck of cards:
Starting with no piles, add the next card from the deck to the first pile with top card greater than the next card from the deck. If the next card from the deck is greater than the top card of all the piles, start a new pile. When the deck is exhausted, collect the cards in order by selecting the smallest visible card at each step.
For instance, consider sorting the list (4 3 9 1 5 2 7 8 6). The first stack gets 4 and 3. Since 9 is larger than 3, it starts a second stack, 1 goes on the first stack, then 5 and 2 go on the second stack. At this point the first stack (top to bottom) consists of (1 3 4), the second stack consists of (2 5 9), and the remaining deck consists of (7 8 6). Now 7 goes on a third stack, 8 goes on a fourth stack, and 6 goes on top of the 7 in the third stack. With all the cards dealt, 1 is collected from the first stack, 2 from the second stack, 3 and 4 from the first stack, 5 from the second stack, 6 and 7 from the third stack, 8 from the fourth stack, and 9 from the second stack. The algorithm has complexity O(n log n).
Your task is to implement the patience sorting algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
use strict; my @Q = qw(4 3 9 1 5 2 7 8 6); my $cols = []; foreach (@Q) { my $f = 0; $f++ while $f<@{$cols} && $_ > $cols->[$f][0]; unshift @{$cols->[$f]},$_; ## Going to use unshift so stacks stored upside down! } my @res; while(@{$cols}) { my( $m_s, $min, $s ) = ( 0, $cols->[0][0], 0 ); foreach( @{$cols} ) { ($m_s,$min) = ($s,$_->[0]) if $_->[0] < $min; $s++; } push @res, shift @{$cols->[$m_s]}; ## shift entry off.... splice @{$cols},$m_s,1 unless @{$cols->[$m_s]}; ## Remove any empty stacks! } print "@res\n";I didn’t think to assume no repeating values — here’s a my version in Swift:
struct PatienceSorter : SequenceType { typealias Generator = PatienceGenerator var stacks: [[Int]] = [] init(_ numbers: [Int]) { numberLoop: for num in numbers { for i in 0..<stacks.count { if stacks[i].last! >= num { stacks[i].append(num) continue numberLoop } } stacks.append([num]) } } func generate() -> PatienceGenerator { return PatienceGenerator(stacks) } struct PatienceGenerator : GeneratorType { var _stacks: [[Int]] init(_ stacks: [[Int]]) { _stacks = stacks } mutating func next() -> Int? { switch _stacks.count { case 0: return nil default: var loweststack = 0 for i in 0..<_stacks.count { if _stacks[i].last! <= _stacks[loweststack].last! { loweststack = i } } let next = _stacks[loweststack].removeLast() if _stacks[loweststack].count == 0 { _stacks.removeAtIndex(loweststack) } return next } } } } let norepeatSort = PatienceSorter(shuffle(Array(1...20))) println(norepeatSort.stacks) // [[9, 8, 6, 3, 2, 1], [14, 13, 12, 4], [15, 5], [20, 17, 11, 7], [19, 16, 10], [18]] println(Array(norepeatSort)) // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] let repeatSort = PatienceSorter([6, 4, 3, 7, 3, 5, 1, 1, 2, 8, 6, 4, 8, 4, 5, 2, 1, 5, 4, 8]) println(repeatSort.stacks) // [[6, 4, 3, 3, 1, 1, 1], [7, 5, 2, 2], [8, 6, 4, 4, 4], [8, 5, 5], [8]] println(Array(repeatSort)) // [1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 8, 8, 8]The problem says to add an item to the top of a pile if it is smaller that
the current top of the pile. However, it is more efficient to append an item
to the end of a list, so this function adds an item to the bottom of a pile
(end of a list), if it is greater than the current bottom of the pile.
from heapq import merge def psort(seq): piles = [] for item in seq: for pile in piles: if item > pile[-1]: pile.append(item) break else: piles.append([item]) return list(merge(*piles))#include
#include
#include
using namespace std;
bool try_insert(vector<vector> &piles, int x)
{
if (piles.size() == 0)
return false;
for (auto &pile: piles)
{
if (x <= pile.back())
{
pile.push_back(x);
return true;
}
}
return false;
}
int pop_least(vector<vector> &piles)
{
int least, least_i;
for (int i = 0; i < piles.size(); i++)
{
if (i == 0)
least_i = i, least = piles[i].back();
else if (piles[i].back() < least)
least_i = i, least = piles[i].back();
}
piles[least_i].pop_back();
if (piles[least_i].size() == 0) piles.erase(piles.begin() + least_i);
return least;
}
void patience_sort(vector &v)
{
vector<vector> piles;
for (int i = 0; i < v.size(); i++)
{
if(!try_insert(piles, v[i]))
piles.push_back(vector{v[i]});
}
for (int i = 0; i < v.size(); i++)
v[i] = pop_least(piles);
}
int main(void)
{
int n;
cout <> n;
cout <<"Elements: ";
vector v;
int tmp;
for (int i = 0; i >tmp;
v.push_back(tmp);
}
patience_sort(v);
for (int x: v)
cout << x <<" ";
cout <<endl;
}
Cool problem.
(define (build-stacks deck) (build-stacks-helper deck (list))) (define (build-stacks-with-existing deck stacks) (build-stacks-helper deck stacks)) (define (build-stacks-helper deck stacks) (define (aux deck buffer stacks) (cond ((null? deck) stacks) ; no cards left in deck ((null? stacks) ; add a new stack ;; recurse ;; remove top card from deck ;; buffer is empty because we are adding a stack ;; append new stack to the END of any stacks we were already holding ;; in buffer (aux (cdr deck) (list) (reverse (cons (list (car deck)) buffer)))) ((< (car deck) (caar stacks)) ; card should go in this stack ;; recurse ;; remove top card from deck ;; buffer is empty because we are adding to an existing stack ;; insert card into existing stack between to remainder of ;; stacks and any cards we have stored in buffer (aux (cdr deck) (list) (append (reverse buffer) (list (cons (car deck) (car stacks))) (cdr stacks)))) (else ; wrong stack ;; recurse ;; deck stays the same ;; add the current stack to the buffer ;; look at next stack (aux deck (cons (car stacks) buffer) (cdr stacks))))) (aux deck (list) stacks)) ; sorting ; since all of the stacks are held in increasing order by the above code ; we can "sort" by taking the top value from the first stack then ; re-build the remainder of the first stack over the other stacks (define (sort-stacks deck) (define (aux sorted-deck stacks) (display sorted-deck) (newline) (display stacks) (newline) (if (null? stacks) sorted-deck (aux (append sorted-deck (list (caar stacks))) (build-stacks-with-existing (reverse (cdar stacks)) (cdr stacks))))) (aux (list) (build-stacks deck))) (define deck '(4 3 9 1 5 2 7 8 6)) (sort-stacks deck) ;; () ;; ((1 3 4) (2 5 9) (6 7) (8)) ;;(1) ;; ((2 5 9) (3 4 6 7) (8)) ;; (1 2) ;; ((3 4 6 7) (5 8) (9)) ;; (1 2 3) ;; ((4 5 8) (6 7 9)) ;; (1 2 3 4) ;; ((5 6 7 9) (8)) ;; (1 2 3 4 5) ;; ((6 7 8) (9)) ;; (1 2 3 4 5 6) ;; ((7 8 9)) ;; (1 2 3 4 5 6 7) ;; ((8 9)) ;; (1 2 3 4 5 6 7 8) ;; ((9)) ;; (1 2 3 4 5 6 7 8 9) ;; () ;;(1 2 3 4 5 6 7 8 9)Java:
public static <T extends Comparable> List sort(List list) {
List<Stack> stacks = newArrayList();
for (T next : list) {
Stack stackForNext = null;
for (Stack stack : stacks) {
if (next.compareTo(stack.peek()) < 0) {
stackForNext = stack;
break;
}
}
if (stackForNext == null) {
stackForNext = new Stack();
stacks.add(stackForNext);
}
// System.out.println("push " + next + " -> " + stackForNext);
stackForNext.push(next);
// System.out.println(" " + stacks);
}
List sortedList = newArrayList();
for (int i = 0; i < list.size(); i++) {
Stack stackWithSmallest = null;
for (Stack stack : stacks) {
if (stackWithSmallest == null || stackWithSmallest.size() == 0
|| (stack.size() > 0 && stack.peek().compareTo(stackWithSmallest.peek()) < 0)) {
stackWithSmallest = stack;
}
}
sortedList.add(stackWithSmallest.pop());
}
return sortedList;
}
Sorry, didn’t read the Howto.
In Java
Is it possible to edit a comment?
Thanks Andras
Another Python solution:
def patience_sort(items):
piles = []
while items:
x = items.pop(0)
added = False
for p in piles:
if p[0] > x:
p.insert(0, x)
added = True
break
if not added:
p = [x]
piles.append(p)
sorted_items = []
while piles:
min_pile, min_item = None, None
for p in piles:
if not min_pile or p[0] < min_item:
min_pile = p
min_item = p[0]
sorted_items.append(min_item)
min_pile.pop(0)
if not min_pile:
piles.remove(min_pile)
return sorted_items
if __name__ == '__main__':
print(patience_sort([4, 3, 9, 1, 5, 2, 7, 8, 6]))
[/sourcecode}
Fix formatting:
def patience_sort(items): piles = [] while items: x = items.pop(0) added = False for p in piles: if p[0] > x: p.insert(0, x) added = True break if not added: p = [x] piles.append(p) sorted_items = [] while piles: min_pile, min_item = None, None for p in piles: if not min_pile or p[0] < min_item: min_pile = p min_item = p[0] sorted_items.append(min_item) min_pile.pop(0) if not min_pile: piles.remove(min_pile) return sorted_items if __name__ == '__main__': print(patience_sort([4, 3, 9, 1, 5, 2, 7, 8, 6]))