<wh*@hotmail.com> wrote in message

news:kg********************************@4ax.com...

Hi,

just been curious. i have learn that quicksorting algorithm is more

widely used then heapsort, despite having the same performance

indication of O(n log n)

anyone knows why?

newbie

Hello newbie,

Quicksort and HeapSort actually differ in behaviour. HeapSort has a

worst-case behaviour that is also N log2(n) where QuickSort has a worst-case

behaviourt of N^2. However, usually average-case is more important than

worst-case and in that case both are N log2(N).

For a particaluar N on average HeapSort will do more work than QuickSort.

The amount of work has the same growth pattern when N increases but it stays

higher. If you look at the algorithms in detail you will see that the number

of element comparisons and exchanges are higher for HeapSort than QuickSort.

Roughly said, HeapSort does two traversals of the data where QuickSort does

only one. A constant factor is always left out of behaviour formalas since

they tend to not be significant for large N on non-lineair algorithms.

By the way, HeapSort is the result of "heapifying" a lineair data structure

into a priority-queue (according to some ordering creteria) and then

"popping" off the elements in order of priority. This makes for a sorting

algorithm but also for an efficient way of implementing a priority queue.

QuickSort is purely a sorting algorithm. Besides that, QuickSort is

inherently recursive where HeapSort is not. Recursion can off course always

be factored out (although QuickSort contains left-recursion).

In combination with the better worst-case behaviour this all makes HeapSort

more interesting from a theoretical point of view IMHO.

Regards,

Silvio Bierman