Thread: How to read heapsort results

Originally Posted by MartinR

Reading from 1 to 10 doesn't work

But of course: that is not how heap sort works. If you take a quick look at the DADS entry for heapsort: "A sort algorithm that builds a heap, then repeatedly extracts the maximum item."

Originally Posted by MartinR

the book I read shows algorithms comparison table in which quicksort is at best case as fast as heap sort but is definitely slower than qsort in worst case. Then they says that well implement quick sort beats heapsort. Hmm how is this possible if quick sort best case performance is just as good as heapsort ?

If you are concerned about best case time complexity for a comparison-based sorting algorithm, then you can always make a single pass before starting the sort proper to check if the sequence is sorted, upon which you have a best case time complexity of O(n).

So, perhaps what you find more strange is that the average case time complexity for heapsort and quicksort is the same, yet in practice quicksort tends to beat heapsort. For this, recall that the Big-O notation in which the time complexity is expressed leaves out constant terms, yet these terms can matter, e.g., if you always make one pass over the sequence, the time complexity is O(n), but if you always make 1000 passes over the sequence, the time complexity is still O(n), yet it is reasonable to expect the former to beat the latter for the same input if the work done on each pass is roughly the same.