Mail Archives: djgpp/1998/04/29/18:52:22
At 12:37 4/29/1998 +0200, Francois Charton wrote:
>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.
Here's another $0.02, despite the fact that I know very little about sorting
algorithms:
The GNU C library uses an algorithm called mergesort, which as far as I have
been able to gather is faster than either, though it requires some memory
overhead.
Incidentally, aren't there some adjustments you can make to quicksort to
eliminate the worst-case behavior?
Another point is that anybody who *really* cares about the speed of their
sort shouldn't be using `qsort' anyway, but their own algorithm which takes
their application into account.
Nate Eldredge
nate AT cartsys DOT com
- Raw text -