Mail Archives: djgpp/1998/04/29/15:03:59
Eli Zaretskii wrote:
>
> 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.
The DJGPP implementation of qsort uses the so-called "median-of-three"
quicksort, which is one of the fastest general-purpose sort algorithms.
However, there have been papers in the literature showing pathological
examples where even the "median-of-three" flavor of quicksort can be
O(n^2). Fortunately, the mean sort time on randomly-chosen arrays is
still O(n log n). See Donald Knuth, _The Art of Computer Programming_
vol. 3, for a more extensive discussion.
ANSI/ISO 9899-1990 does not specify the algorithm to be used to
implement qsort, so either quicksort or heapsort could be used. In my
opinion, median-of-three quicksort is generally a better choice, since
it tends to be faster. If there's a situation where an untimely solution
to a sorting problem could cause injury or damage to property, then
heapsort is a better choice, owing to its O(n log n) worst-case
behavior, but it shouldn't be imposed on everyone else, because, on the
average, it will slow us down!
As far as the DJGPP implementation of qsort is concerned, I am actually
more worried about a problem I discovered a while ago, when I attempted
to use qsort to do a sort based on floating-point values. Due to the
optimizer storing one comparison value in memory, and leaving the other
in the coprocessor stack to higher precision, the results of the
comparison were sometimes inconsistent for equal or nearly-equal
comparison values.
This would have been OK, if it had only resulted in nearly-equal
elements being sorted in arbitrary order, into the proper contiguous
region of the array, but I found that some implementations produced an
array overflow (DJGPP was among them). Since there is nothing in
ANSI/ISO 9899-1990 which defines the behavior under such circumstances,
this is not a bug in qsort (but rather in my comparison routine), so I
didn't submit a bug report, but it is definitely a
quality-of-implementation issue. I got around the problem by using
volatile variables, but it still made me nervous, and I wondered if
there were some way qsort could be rewritten to avoid this potential
problem.
-Eric Rudd
rudd AT cyberoptics DOT com
- Raw text -