Mail Archives: djgpp/1998/04/29/03:47:03
On Tue, 28 Apr 1998, Kbwms wrote:
> The standard library utility qsort() exhibits the dreaded quadratic
> behavior on some sort targets. Some years ago, I wrote a program
> that tests sort functions. The program was described in an article
> that was published in an issue of C/C++ Users Journal. Here is what
> my test says when qsort() is run on various kinds of targets, each
> 20,000 in size:
Thanks, this is all very educational.
However, I'm puzzled what is it exactly that you are trying to say
here? Are you telling that the DJGPP's version of `qsort' is
intolerably slow in some cases? Then let's see comparison to more
than a single other implementation, and let's discuss how `qsort' can
be made faster in these cases. Do you have a patch to suggest that
will make `qsort' it faster? If so, please post that patch. Do you
have an alternative version of `qsort' whose source is freely
available and which you suggest to include in the next release of
DJGPP? If so, either post that source or point us to where it can be
obtained.
If your only intent was to post results of testing a function, IMHO
some results from other implementations (more that a single unnamed
alternative) should also be published, to put the measured data in
some perspective.
Publishing results with no clear summary (like ``this is too slow, and
here's the evidence'') tends to confuse newcomers who don't have any
prior knowledge of the subject matter. You already had such a case
after your previous posting about testing `rand'.
FYI, the version of `qsort' in the DJGPP library uses a slightly
modified algortithm for picking up the first element, which is better
in some pathological cases. See the library sources for more details.
- Raw text -