Mail Archives: djgpp/1998/04/29/07:11:05
Eli Zaretskii wrote:
>
> If somebody has a better implementation of `qsort' which is free (not
> GPL/LGPL), please point to it. Failing that, we will need to wait until
> somebody becomes so annoyed by the current implementation that he/she
> actually sits down, corrects it, and submits the patches to DJ Delorie.
>
For those who do not want to run the (very small) risk of one of
these N^2 cases (when qsort() becomes very slow) happening, an
alternative algorithm which always exhibits O(n log(n)) behaviour is
heapsort.
It performs more slowly than qsort on average the result of one benchmark
(available at
http://www.cbl.ncsu.edu/publications/1997--Talk-12-Kapur/1997--Talk-12-Kapur-HTML/node7.html)
showed that Heapsort takes on average 3,9 N log(N) comparisons per
sorting of N elements, while qsort only takes 2,3 N log(N), which makes
heapsort about 1,5 times slower than qsort. However, heapsort is
guaranteed to be O(nlog(n)).
Implementations in C of heapsort are fairly easy to find in textbooks or
on the net.
Francois
- Raw text -