Take a deck of cards labeled 1, 2, 3, … , n. The deck is shuffled, cards are turned up one at a time and dealt into piles on the table, according to the rule
A low card may be placed on a higher card (e.g. 2 may be placed on 7), or may be put into a new pile to the right of the existing piles.
At each stage we see the top card on each pile. If the turned up card is higher than the cards showing, then it must be put into a new pile to the right of the others. The object of the game is to finish with as few piles as possible.
played with the greedy strategy, i.e., placing each new card on the leftmost pile that is legally possible to use. At each stage of the game, under this strategy, the labels on the top cards of the piles are increasing from left to right. To recover the sorted sequence, repeatedly remove the minimum visible card.
Read full article from Patience sorting - Wikipedia, the free encyclopedia
A low card may be placed on a higher card (e.g. 2 may be placed on 7), or may be put into a new pile to the right of the existing piles.
At each stage we see the top card on each pile. If the turned up card is higher than the cards showing, then it must be put into a new pile to the right of the others. The object of the game is to finish with as few piles as possible.
public static <E extends Comparable<? super E>> void sort (E[] n) { List<Pile<E>> piles = new ArrayList<Pile<E>>(); // sort into piles for (E x : n) { Pile<E> newPile = new Pile<E>(); newPile.push(x); int i = Collections.binarySearch(piles, newPile); if (i < 0) i = ~i; if (i != piles.size()) piles.get(i).push(x); else piles.add(newPile); } System.out.println("longest increasing subsequence has length = " + piles.size()); // priority queue allows us to retrieve least pile efficiently PriorityQueue<Pile<E>> heap = new PriorityQueue<Pile<E>>(piles); for (int c = 0; c < n.length; c++) { Pile<E> smallPile = heap.poll(); n[c] = smallPile.pop(); if (!smallPile.isEmpty()) heap.offer(smallPile); } assert(heap.isEmpty()); } private static class Pile<E extends Comparable<? super E>> extends Stack<E> implements Comparable<Pile<E>> { public int compareTo(Pile<E> y) { return peek().compareTo(y.peek()); } }Also so refer to http://wordaligned.org/articles/patience-sort.html
Read full article from Patience sorting - Wikipedia, the free encyclopedia