424,952 Members | 1,665 Online
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 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
5 Replies

 P: n/a 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: 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). 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" wrote in message news:c2**********@sun-cc204.lut.ac.uk... Silvio Bierman wrote: 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). 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 Thanks for your enlightenment :) On Tue, 2 Mar 2004 15:17:27 +0100, "Silvio Bierman" wrotE: wrote in messagenews: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? newbieHello newbie,Quicksort and HeapSort actually differ in behaviour. HeapSort has aworst-case behaviour that is also N log2(n) where QuickSort has a worst-casebehaviourt of N^2. However, usually average-case is more important thanworst-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 stayshigher. If you look at the algorithms in detail you will see that the numberof element comparisons and exchanges are higher for HeapSort than QuickSort.Roughly said, HeapSort does two traversals of the data where QuickSort doesonly one. A constant factor is always left out of behaviour formalas sincethey tend to not be significant for large N on non-lineair algorithms.By the way, HeapSort is the result of "heapifying" a lineair data structureinto a priority-queue (according to some ordering creteria) and then"popping" off the elements in order of priority. This makes for a sortingalgorithm but also for an efficient way of implementing a priority queue.QuickSort is purely a sorting algorithm. Besides that, QuickSort isinherently recursive where HeapSort is not. Recursion can off course alwaysbe factored out (although QuickSort contains left-recursion).In combination with the better worst-case behaviour this all makes HeapSortmore 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.