qsort

[Richard O'Keefe]

In article <860 at maytag.waterloo.edu>, lhf at aries5 (Luiz H de Figueiredo) writes:
> In a recent thread about sorting strings, someone suggested that qsort was
> not the way to go because quicksort is not very good for nearly ordered files.
> My question is:
> 	Does qsort have to implement quicksort?

The standard will let an implementor code qsort() any way he likes.
It's worth checking your manual to find out what you actually have.
My manual says
	qsort() is an implementation of the quicker-sort algorithm.
which is what the UNIX manual has said since V7.  I've come across
one PC version which used Shell sort.

> What is more useful to assume is that qsort is *very* efficient, so that we
> don't have to re-invent the wheel every day.

It is not useful to assume that qsort is *very* efficient, because whenever
I have tested it I have found that it *isn't*.  On UNIX systems, my merge-
sort typically runs about 30% faster than qsort(), and I _know_ my code can
be improved.

What *IS* useful is to assume that qsort() is THERE.  In most programs even
the cost of qsort() is a small fraction of the total cost of the program.
So what you do is write your program using qsort() -- because it is there --
and then profile it -- because it isn't very fast -- and IF the sort turns
out to be taking a lot of time, FIRST you try very hard to make your
comparison function fast, and THEN if a 30% improvement is going to help
you look at replacing qsort().

If you have a complicated comparison function, a good trick is to make a
pass over the array generating a new key which is easier to compare.
For example, if you want to sort "MM/DD/YY stuff" it is worth recoding
it as "YYmdstuff" where m and d are single characters, and then you can
use one strcmp() instead of more complicated code.