Talk:Heapsort

From Academic Kids

Numerical Recipies copyright

Is it acceptable to use code adapted from Numerical Recipies in C? I don't own a copy, so I can't quote it, but I am led to understand that it is very restrictive in its usage licence. — PhilHibbs | talk

That's correct. The code can only be used on one screen if you purchase a single-screen license; distribution is prohibited. Deco 00:27, 27 Apr 2005 (UTC)

Pseudocode question

I'm fairly certain that the pseudocode in this article does not work on some arrays of odd length. That is, if length(<math>a<math>) is odd, then occassionally heapSort(<math>a<math>) produces an array that is one swap away from sorted. For example,

 heapSort([1,2,3]) -> [1,3,2]

and

 heapSort([2,1,3,5,4]) -> [1,2,4,3,5].

If, in heapSort, I replace the line

   var int start := count / 2 - 1

with

   var int start := count / 2

it seems to correct the bug. Have I missed something? --Quaternion 22:28, 18 Feb 2005 (UTC)

---

Is it for some reason impractical to implement a quaternary heapsort?

It's not impractical to implement a quaternary heapsort. In fact, I managed to implement an N-ary Heapsort algorithm in Java. — pguedes

---

i think there's a bug in the final line of the python program. should it not be called with the first element of the array, 1 instead of with 0?

---

To my mind O(N log N) is not approximately linear for large N, but I suppose it depends on your viewpoint. There are sort methods which are linear - e.g pigeon hole sort for a densely populated set of integers, and these could be expected to run significantly faster.

However, both heapsort and quicksort are, for most practical purposes, amongst the fastest sorts. Note that scrambling the elements before doing a quicksort is often more effective - as often the elements are almost in order, in which case quicksort is known to be slow. This does not apply to heapsort.

I agree with the O(N log N) statement, and eliminated the claim that it's about linear. Scrambling the elements isn't a really effective strategy for improving quicksort, since scrambling involves a lot of cache misses, making it a very slow operation. Deco 19:36, 4 Nov 2004 (UTC)

---

The article states that an in-place (O(1) auxiliary space) quicksort is possible. Is that true? Don't you need a stack to manage what parts of the array you still need to sort? --Ryan Stone 15:52, 4 Nov 2004 (UTC)

Oh, I see it now. The data stored on the stack in quicksort is the pivot positions. It is quite possible to compute, rather than store, the pivot positions, in restricted implementations — for example, in a quicksort implementation which always uses the median. I'm not aware of any fast in-place quicksort variant though. Deco 19:31, 4 Nov 2004 (UTC)

---

There is something I've always wondered about heapsort. When you've created the heap and starts to extract the largest element of it, you swap it with the element with the largest index in the heap to get the value in the right position (ie when you just have created the heap, the first thing you do is to swap the 1st element with the Nth, then heapify, then you swap the 1st element with the (N-1)th and heapify and so on). But if you do that you will most of a time get a very low value at the top of the heap (since the value was previously at the bottom of the heap), and since that value is pretty low the siftup will take longer. Why don't you instead implement the heap as a min-heap instead of a max-heap? Then the head would be at the right position directly (no need to swap) and you could make one of it's children (the element just after it) the head and then heapify. The heapifying would take shorter time on average wouldn't it? I mean, it obvoiusly wouldn't be asymptotically faster, but it would be faster, n'est pas? Gkhan 01:21, Feb 14, 2005 (UTC)

And oh yeah, I realize that the talk-page isn't really the right forum for asking techincal questions, but indulge me Gkhan 01:22, Feb 14, 2005 (UTC)

Note: I removed my previous answer here -- I had the algorithm Gkhan was describing completely wrong

Put briefly, the algorithm you describe isn't very effective at all -- assymptotically it's worse than Bubble sort. Actually, what you describe is an expensive version of Selection sort.

Here's the reason why it's so poor: The heapifying operation takes O(n log n). What you're suggesting is that we heapify n elements, then n - 1 elements, ... until finally heapifying an array with 1 element(ok, we could skip that, but it doesn't make too much of a difference, and does make the calculations below easier.

The number of operations we do will thus be O(n log n) + O ( (n - 1) log (n - 1) ) + ... + O ( 1 log 1)

So it's O ( sum(i = 1 to n) of i log i). I'm not if that can be simplified, but I do know that sum(i = 1 to n) of i is n(n + 1)/2. So your algorithm will be worse than O (n ^ 2).

I don't think that on average, things will be much faster. Let me think about it and see if I can come up with an answer for that.--Ryan Stone 21:03, 18 Feb 2005 (UTC)

Well, I've thought about this a bit more, and what I realized was that even if Gkhan's algorithm was faster in the average case, it still probably couldn't beat quicksort. Heapsort's greatest advantages over quicksort is its guaranteed O (n log n) and that it's an in-place sort. If you're willing accept poor performance on certain inputs anyway, you might as well go with quicksort.--Ryan Stone 02:08, 23 Feb 2005 (UTC)