Heap sort status 1973 
Author Message
 Heap sort status 1973

I have volume 3 of Knuth's "Sorting and Searching" text.
It states that the Heap sort algorithm is incomplete (and unstable).

Is there an updated version of this algorithm available?

db.



Sat, 11 Apr 1998 03:00:00 GMT  
 Heap sort status 1973
Quote:

>I have volume 3 of Knuth's "Sorting and Searching" text.
>It states that the Heap sort algorithm is incomplete (and unstable).

>Is there an updated version of this algorithm available?

>db.

If you modify the comparison of keys appropriately, you can make it
stable. Here's what you do (thanks to Peter Wooster, who ran into
this some years back himself):

When you are comparing two keys, if they are EQUAL, look further
at the indices of the keys, and pick the LOWER index as being
the "bigger" key [if your heap sifts biggest to top].

There is a somewhat more readable version of heapsort in
"Numerical Recipes in C", but it also contains the instability
problem. If you amend the algorithm as above, it should work properly.

Bob



Sun, 12 Apr 1998 03:00:00 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. Anyone w/ KUESTER & MIZE text, circa 1973

2. heap sort in 68k ?

3. Ada generics / GNAT Heap-sort

4. Return Values vs Status Queries vs Status Messages

5. Sort (List sorts...)

6. UNIX sort exponents (bc|sort)

7. Binary Sort/Merge Sort in awk

8. ANN: New release of S.C.A. Micro Templates (Browse Header Sort and Reverse Sort Template)

9. Sort of Sorts

10. All Sorts of Sorts

11. All Sorts of Sorts

12. All Sorts of Sorts

 

 
Powered by phpBB® Forum Software