Re: smuggling data in and out of alarm handlers and the like

On Jan 3, 2:53 pm, Tor Rustad <see....@xxxxxxxxxxxxxxxx> wrote:
Keith Thompson wrote:

[...]

Of course not -- but it's code that *I* don't have to write. A bug in
a sort routine that I write (and test as much as I have time for) is
more likely than a bug in a vendor's qsort() routine that's been used
by zillions [*] of other programmers.  That's not to say that a bug in a
vendor's code is impossible, of course.

I've never heard of a buggy qsort() in a released implementation of
the C standard library.  Have you?

I wouldn't trust the system privided qsort() with my life, in such a
case, I would run my own implementation for sure.

A couple of years ago, I actually wrote a sort benchmark to compare the
performance of different algorithms. In at least one of these test
cases, it triggered an unstable sort in... IIRC Microsoft's qsort()
implementation.

The Microsoft qsort implementation is a version of Singleton's sort.
An older version had some safety checks in it for the quadratic cases:
1. In-order partition
2. Reversed partition
I noticed (several years ago) that the safety checks were removed. I
was working as a subcontractor at MS at the time, so I called the guy
who did it on the phone.
I asked him why the checks were removed. He said that they did not
make the code run any faster. I told him that the reason they were
there was for certain degenerate cases that can make the sort go
quadratic. He wasn't too interested. I looked today, and the checks
still are not in there (though there have been a few small
improvements since the last time I looked).

P. J. Plauger has written a very nice introspective sort. For a
general qsort() interface, I don't think you can do much better since
it never goes quadratic.

IMO, for serious sort jobs, qsort() is a bad candidate, since it's a QoI
issue, weather the standard library implementation is stable or not.
OTOH, I can agree that non-expert replacements of qsort(), often are
worse, just as non-expert replacements of rand() are.

You just got an 'Amen!' from the congregation.
.

Relevant Pages

  • Re: smuggling data in and out of alarm handlers and the like
    ... a sort routine that I write is ... more likely than a bug in a vendor's qsort() routine that's been used ... I actually wrote a sort benchmark to compare the performance of different algorithms. ...
    (comp.lang.c)
  • Re: smuggling data in and out of alarm handlers and the like
    ... make you realize that the sort function should be a macro, ... This allows your "cmp" to itself be a macro, ... Clearly the cmp operation used by qsort() can't be a macro, ... void * context, ...
    (comp.lang.c)
  • Re: qsort
    ... >>A simple example is an insertion sort. ... Essentially one element moves along the array until it is in its ... > fail but qsort() cannot. ... without having any kind of dynamic memory allocation ...
    (comp.lang.c)
  • Re: smuggling data in and out of alarm handlers and the like
    ... it triggered an unstable sort in... ... Software exploratorium: The trouble with qsort. ... about the Quicksort algorithm; the first does acknowledge that qsort ... sort algorithm under the covers in the final analysis. ...
    (comp.lang.c)
  • Re: C Pointers
    ... Make a singly linked list and apply merge sort. ... But qsort is a standard function, that you do not have to implement. ... Using qsortand strcmp, as suggested before, ... Also, the input is an array, not a linked list, and a good assumption ...
    (comp.lang.c)