The worst case is of course infinityOriginally posted by Salem
Yeah, actually it doesn't have an O value as such.
It is a probablility, that being 1 : N! of actually coming up with the right answer in any given trial.
The average time till success is N!.
Let NS be the time to success ( i.e., getting a sorted deck).It is easy to see that
P(NS=i)=(1-(1/N!))^(i-1) * (1/N!)
The expected value of NS is N!
The one who says it cannot be done should never interrupt the one who is doing it.
In case someone cared about the real answer (which is not very well known, or understood):
1. O'Hare's Quicksort algorithm has a worst case of O(n^2) running time. (I.e., its not much better than bubble sort.) It requires O(log(n)) storage. Quicksort has a good reputation because it has an average running time of O(n*log(n)) and on average outperforms other algorithms with O(n*log(n)) performance.
2. Heapsort has a worst case running time of O(n*log(n)). Heapsort requires an additional storage of O(log(n)). On average, however, quicksort substantially outperforms heapsort.
3. Mergesort has a worst case running time of O(n*log(n)). Mergesort requires an additional storage of O(n). On average mergesort is about as fast as quicksort, but can lose badly in special cases where the allocating so much more memory forces the data to leave the closest CPU cache.
4. Shellsort is at most O(n*log(n)^2) -- however the best lower bound has not yet been determined. If I recall correctly, it requires only O(1) additional storage.
5. Shakersort, bubblesort and insertion sort all have a performance of about O(n^2).
6. Radix sort or bin sort have worst case running times of O(n^2), and can have enormous memory storage requirements. These sorts are used when you can model the distribution of the input elements farily well (like for a phone book, or numbers that fall into a specific range) and will have an average running time of nearly O(n) in these "good" cases.
7. A relatively new algorithm called Introspective Sort has a worse case running time of O(n*log(n)). It has an additional storage requirement of O(log(n)). On average it performs identically to quicksort. This sort which has only been described in a handful of papers can be generally described as a hybrid of quick sort and heap sort. Basically the algorithm runs quicksort for a while and if it figures its taking too long, then it just switches to heap sort -- it does the decision making between the two algorithms when the quicksort is recursing too deeply. Introspective sort is as complicated to implement as implementing both quicksort and heapsort.
On balance, the Introspective Sort is the one with the best performance and least memory requirements. Mergesort would be roughly tied in performance and is easy to implement but requires a big malloc. Quicksort works well in practice and is also easy to implement, (ignoring the fact that most C compilers come with a quicksort implementation that you can use) by I personally avoid it because of its worst case running time. Bubble sort and shakersort are actually pretty good if the data is already mostly sorted and can even out-perform quicksort in those cases. For applications where it works, its impossible to beat radix or bin sort.
Personally, I usually use merge sort unless I have a compelling reason not to.
>which is not very well known, or understood
Now you're just generalizing.
>I personally avoid it because of its worst case running time
You must also be ignoring the fact that the worst case can be made infinitely rare if you do a little more work than the basic algorithm.
>Personally, I usually use merge sort unless I have a compelling reason not to.
As always the big three for sorting determine your choice: speed, space, and stability. Merge sort is efficient, is easy to implement for linked data structures and external data sets, and is stable. However, if I have to write my own routine, I'll use one of the primitive sorts until I know that something more sophisticated is needed.
[edit]
By the way, I think you meant C. A. R. Hoare when speaking of quicksort. Unless you're talking about some variation of the original algorithm devised by someone else.
[/edit]
Last edited by Prelude; 03-17-2004 at 09:53 PM.
My best code is written with the delete key.
qsort need not be implemented as quicksort, the C standard does not specify the algorithm with which to implement qsort. The name is suggestive though.Originally posted by qed
I(ignoring the fact that most C compilers come with a quicksort implementation that you can use)
The one who says it cannot be done should never interrupt the one who is doing it.
Infinite has a specific mathematical meaning. And it doesn't fit in this case. Its not even close.>I personally avoid it because of its worst case running time
You must also be ignoring the fact that the worst case can be made infinitely rare if you do a little more work than the basic algorithm.
Median of 3, 5, etc, reduces that number of bad cases, but cannot remove them. Specifically increasing the number of median samples has linear impact on performance, however has a logarithmic affect on reducing the number of bad cases.
Random pivot point selection can work a lot better, but will dramatically reduce performance.
If you really want to good properties of quicksort, the right answer is to use Introspective sort which makes the right decision -- do the quick sort for a while but bail out when its quite possibly taking too long and use heapsort.
This goes to my point about not understanding the state of sorting -- if you want high-performance and in-place you have to go with Introsort and if you want simplicity you should go with mergesort. Actually chosing a raw quick sort (with the media tricks or whatever) is just a bad compromise. IMHO, quicksort is officially obsolete.
>Infinite has a specific mathematical meaning. And it doesn't fit in this case. Its not even close.
I wasn't using the mathematical meaning, but nice try.
>This goes to my point about not understanding the state of sorting
How does that go to your point about my not understanding the state of sorting?
>if you want high-performance and in-place you have to go with Introsort
No, you don't have to do anything of the sort. You choose the best algorithm to fit your needs. In an unrelated example, I wouldn't dream of using an iterative AVL tree because it provides the best guarantees of the balanced trees if my data will almost always be inserted randomly. It isn't worth the effort of implementing, testing and debugging a quicksort/heapsort combination unless you are writing a generic library function like qsort or you expect the pathological cases on a regular basis. This is a prime example of people overcomplicating problems by blindly using what they think is always the best solution.
>and if you want simplicity you should go with mergesort
You're making the same mistake here too. Sophisticated sorting methods are not always the best option. I've had many situations where insertion sort would outperform quicksort, mergesort, heapsort, etc...Had I blindly used mergesort as you seem to do, it could have been a detriment to performance.
I applaud your understanding of sorting theory, not many people are willing to learn more than bubble sort, insertion sort and quicksort. However, theory and practice are often different. A weak algorithm can outperform a strong one, a stupid algorithm can work for all reasonable cases, the worst case could be so rare as to make the effort of protecting against it not worth the time and money. You're generalizing in a field of programming that cannot be generalized. It has to be taken on a case by case basis.
Your first post was correct and valid for the question asked. My reply added to yours and was also correct and valid. I still don't understand what your problem with it is.
Last edited by Prelude; 03-18-2004 at 08:38 AM.
My best code is written with the delete key.
