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

I didn’t think to assume no repeating values — here’s a my version in Swift:

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.

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

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: