Both quicksort and heapsort do in-place sorting. Which is better? What are the applications and cases in which either is preferred?
+5
A:
http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html has some analysis.
Also, from Wikipedia:
The most direct competitor of quicksort is heapsort. Heapsort is typically somewhat slower than quicksort, but the worst-case running time is always Θ(nlogn). Quicksort is usually faster, though there remains the chance of worst case performance except in the introsort variant, which switches to heapsort when a bad case is detected. If it is known in advance that heapsort is going to be necessary, using it directly will be faster than waiting for introsort to switch to it.
DVK
2010-03-18 05:48:13
A:
Heapsort has the benefit of having a worst running case of O( n log( n )) so in cases where quicksort is likely to be performing poorly ( mostly sorted data sets generally ) heapsort is much preferred.
Mimisbrunnr
2010-03-18 05:48:54
Quicksort only performs poorly on a mostly sorted data set if a poor pivot choosing method is chosen. Namely, the bad pivot choosing method would be to always choose the first or last element as the pivot. If a random pivot is chosen each time and a good method of handling repeated elements is used, the chance of a worst-case quicksort is very small.
Justin Peel
2010-03-18 19:52:23
@Justin - That is very true, I was speaking on a naive implementation.
Mimisbrunnr
2010-03-18 20:30:02
@Justin: True, but the chance of a major slowdown is always there, however slight. For some applications, I might want to ensure O(n log n) behavior, even if it's slower.
David Thornley
2010-03-24 18:50:59
A:
Heapsort builds a heap and then repeatedly extracts the maximum item. Its worst case is O(n log n).
But if you would see the worst case of quick sort, which is O(n2), you would realized that quick sort would be a not-so-good choice for large data.
So this makes sorting is an interesting thing; I believe the reason so many sorting algorithms live today is because all of them are 'best' at their best places. For instance, bubble sort can out perform quick sort if the data is sorted. Or if we know something about the items to be sorted then probably we can do better.
This may not answer your question directly, thought I'd add my two cents.
KMan
2010-03-18 07:43:29