By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,952 Members | 1,665 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,952 IT Pros & Developers. It's quick & easy.

Heapsort and quicksort

P: n/a
why
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
Jul 17 '05 #1
Share this Question
Share on Google+
5 Replies


P: n/a

<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
Jul 17 '05 #2

P: n/a
wh*@hotmail.com wrote:
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?


Because it's easier to understand, I think.

Stewart.

--
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment. Please keep
replies on the 'group where everyone may benefit.
Jul 17 '05 #3

P: n/a
Silvio Bierman wrote:

<snip>
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).

<snip>

I think heapsort is every-case N log2(N). Has anyone figured out the
best-case of quicksort?

But the best algorithm to use depends on the data and its chances of
already being roughly in order. For data that's had bits and bobs of
stuff changed since it was sorted before, bidirectional bubblesort works
well.

OTOH, for sorting a tournament crosstable, where swapping is a
comparatively expensive operation, selection sort would work quite well.

Stewart.

--
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment. Please keep
replies on the 'group where everyone may benefit.
Jul 17 '05 #4

P: n/a

"Stewart Gordon" <sm*******@yahoo.com> wrote in message
news:c2**********@sun-cc204.lut.ac.uk...
Silvio Bierman wrote:

<snip>
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).

<snip>

I think heapsort is every-case N log2(N). Has anyone figured out the
best-case of quicksort?

But the best algorithm to use depends on the data and its chances of
already being roughly in order. For data that's had bits and bobs of
stuff changed since it was sorted before, bidirectional bubblesort works
well.

OTOH, for sorting a tournament crosstable, where swapping is a
comparatively expensive operation, selection sort would work quite well.

Stewart.

--
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment. Please keep
replies on the 'group where everyone may benefit.


HeapSort indeed is always N log2(N). QuickSort best-case can be N but that
depends on the way it is implemented. Many naive implementations show
worst-case behaviour on (almost) sorted input.

When swapping is expensive (which it never is in Java) sorting an array of
indexes/pointers instead of the actual objects can help.

If the data is in a linair linked list various variants of merge-sort can be
very efficient also, especially on partially sorted data.

Silvio

Jul 17 '05 #5

P: n/a
why
Thanks for your enlightenment :)

On Tue, 2 Mar 2004 15:17:27 +0100, "Silvio Bierman"
<sb******@idfix.nl> wrotE:

<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


Jul 17 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.