Talk:Patience sorting

From Wikipedia, the free encyclopedia

Contents 1 Complexity 2 Removed from article 3 Implementation code in C++ 4 bazaar

[edit] Complexity

The upper bound on the algorithm can't possibly be true! How can it be a comparison sort, and have less than O(n log n)? It's not possible! gkhan 12:34, May 28, 2005 (UTC)

I agree with the O(n log n) limit. The algorithm as described seems to have complexity O(n * m), where m is the length of the longest ordered subsequence. I'm not sure what the expected value of m is, but its worst-case is clearly n (if the array is already sorted), making the algorithm O(n^2). I'm not sure how the van Emde Boas tree fits in.

I asked a question about this on comp.programming where I got a satisfactory explanation [1] gkhan 19:47, May 29, 2005 (UTC)

Good call. By that argument, the worst case on gathering is O(n log n). One would think that the complexity to deal would be the same, but in fact you can simply keep track of the largest element seen so far, making sorted input O(n). Bovlb 02:42, 2005 May 30 (UTC)

The van Emde Boas based implementation makes asumptions about the keys range so it is not a comparison sort. Lets talk of arbitrary values and true comparison sorts. Using binary search to build the piles gives a O(n log n) algorithm. For gathering, the wikibooks implementation is not really efficient since it consist of an inteleaving of all the piles (the number of piles can be O(n)) and this can cost O(n²)comparisons (take as initial list). A better implementation can use and preserve the fact that the top of piles are ordered. We can surely do that by insertion of the first pile in the ordered list of piles with respect to the top values ordering, however this will also cost O(n²). Of course, to gather one can forget the structure and apply a O(nlogn) sort at this point, but this can't be called a patience sort. PierreBoudes 15:07, 16 March 2007 (UTC)

[edit] Removed from article

(To play with a regular 52-card deck, some ordering needs to be imposed, arranging the cards within a suit and imposing some order on the suits).'

Tautology. If you play with a regular 52-ccard deck, the ordering is already done for you. Project2501a 13:16, 28 May 2005 (UTC)

I feel that some context introduction is needed; when one is describing a card game, it only makes sense to explain how to play with the regular cards. Even the article [1] doesn't snub the idea of explaining it to the regular card players:

To play with real cards, one needs to linearly order the 52 cards, e.g., by putting suits in the bridge-bidding order . This mindless form of solitaire is then quite playable, perhaps while watching television.

[1], p.3

BACbKA 17:25, 4 April 2006 (UTC)

[edit] Implementation code in C++

Since there seems to be no free software implementation of the patience sorting available, I finally got to posting one myself, in C++ [2]. Currently no veb-trees are implemented, as well as no back-pointer-based sorting recovery, but it's what I myself use for a quick check of what the longest increasing subsequence length in a set is. Comes with some other C++ utilities you might like. --BACbKA 13:34, 12 May 2006 (UTC)

Thanks to User:Egkauston, who pasted a java implementation, I decided to proceed in a more fundamental way and created a patience sorting page on the wikibooks. The java code has been moved over there, and I have pasted excerpts from the above C++ code as well. See the wikibooks link in the article. --BACbKA 23:52, 1 February 2007 (UTC)

[edit] bazaar

I wonder if the fact that bazaar uses patience sort is notable enough in general (if it were, why isn't it on the bazaar article)? If it's notable in the context of the "Patience sorting" article, maybe we should create a new section detailing usage examples in known programs? if yes, what to call it? The reason I am asking is that, currently, I find the bazaar link in the "See also" section a bit sticking out of the general flow of the article, and have no trivial way in mind to smoothen it back. --BACbKA 07:46, 8 February 2007 (UTC)