Talk:Patience sorting

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^{2})$comparisons (take $k,k-1,\ldots ,2,1,k+1,k+2,\ldots ,2k$ 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^{2})$. Of course, to gather one can forget the structure and apply a $O(n\log n)$ sort at this point, but this can't be called a patience sort. PierreBoudes 15:07, 16 March 2007 (UTC)

I think thats exactly the point. Why generating piles and then use a Priority queue like in the Java implementation? You could just use a Priority queue in the first place and don't use the piles. It's like I invent a new sort algorithm named reverseSort: reverse the Input and then use a priority queue. And it just needs $O(n\log n)$ time, wow! Popelmaus (talk) 16:03, 25 April 2012 (UTC)

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 $\clubsuit \diamondsuit \heartsuit \spadesuit$. This mindless form of solitaire is then quite playable, perhaps while watching television.

[1], p.3

BACbKA 17:25, 4 April 2006 (UTC)

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)

Hi, I fixed the C++ code because it used a static function in an empty class. I understand why it's necessary in Java but it is not in C++ : you can use "global" function. Other than that, I was thinking that this function could be adapted in a STL Algorithm stype by using iterators only instead of a vector but it depends on if the algorithm requires random access to elements. That said, it's only an example so it might not be necessary to do that (and maybe make it less obvious to non-C++ programmers ) Anyway I didn't touch the inside of the code. 213.39.33.80 (talk) 12:31, 24 November 2010 (UTC)

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)

I followed the citation and found no information regarding Bazaar using the Patience sorting algorithm. --Edsc86 12:20, 1 November 2009 (UTC)

It was there, but as an open wiki, revctrl.org is not a reliable source. QVVERTYVS (hm?) 13:18, 29 November 2015 (UTC)

WTF?

A whole section devoted to a card game, but no real description of the problem? And why C++ for implementation instead of pseudo-code or some more concise language? —Preceding unsigned comment added by 95.181.12.52 (talk) 14:02, 8 June 2010 (UTC)

I agree. There is too much explicit code for this article. It should be refactored into pseudocode. Resyst (talk) 16:11, 19 September 2015 (UTC)