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.

About these ads

Pages: 1 2

7 Responses to “Patience Sorting”

  1. 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";
    
  2. Nate said

    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]
    
    
  3. Mike said

    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))
    
  4. Ihor Diachenko said

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

  5. mcmillhj said

    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)
    
  6. Andras said

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

  7. Andras said

    Sorry, didn’t read the Howto.
    In Java
    Is it possible to edit a comment?
    Thanks Andras

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: