Thread: Confused about "Patience Sorting"

But why I not directly use heap sort or tree sort if I can use them?

*shrug*

Why not use a general purpose "Quicksort"? Why bother studying "Patience Sort"?

What algorithm you need to use should be determined by how much you know about the data to be sorted and the characteristics you require.

I have never studied "Patience Sort". It may be that, as a sorting algorithm, it is useless when compared to any other sorting algorithm. If so, "Patience Sort" would not be the only sorting algorithm useless for sorting. Many "useless" sorting algorithms are of particular use because of the characteristics of how they sort the data.

Without an extensive study of the performance of the algorithm I have no way of knowing if its characteristics are suitable to sorting a particular "kind" of data.

I just think patience sort has its own way to do that.

I did not say that you had to use a tree or heap.

I also never said that this algorithm was worth implementing.

Soma

But what I want is the "pure" patience sort.

*tsk*

Okay.

Create an array with 2^32 pointers to pointers to your node type and simply use the address as a hash.

Soma

Well, I don't think this is useful. This may help the speed a little, but it's time complexity is still O(nsqrtn). Because for a randomized array of size (n). The number of piles we get is expected to be (sqrtn). So if we don't use any special method(just like a heap) the the complexity of patience sorting will always be O(nsqrtn).

In a word, patience sorting is an O(nsqrtn) algorithm, just like a pool sort.

I won't use this algorithm in real world. I just fond of sorting algorithm which is based on comparison. I have collect about 30 sorting algorithms now.

I also have a program which animates each algorithm, where you can race them against one another (they run in separate threads) and give them different initial sort orders etc.

I was working on something similar a while back. (Some recent developments pushed that project back.)

Are you doing any benchmarks? Or is this just a visual demonstration? What kind of data do you use?

Soma