Mail Archives: djgpp/1998/04/29/04:43:51
On Wed, 29 Apr 1998, Michel Julier wrote:
> As far as I know it, the QSORT algorithm is "generally" fast, but in
> some special cases, that shouldn't occur often "by chance", it can be
> very slow, indeed N^2.
AFAIK, the DJGPP version handles some of these cases by avoiding the
quadratic behavior.
> If you are looking for algorithms that are
> always fast, even in pathological cases, you'll have to look for a
> completely different algorithm, possibly a more complex one or one that
> requires a few extra bytes or memory per item, or maybe that has a larger
> constant factor for the time spent "constant * n * log(n)".
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.
Since DJGPP is run by volunteers on their free time, nothing here gets
done without interested individual(s) willing to invest their time and
talent into improving DJGPP.
- Raw text -