Newsgroups: comp.lang.c
Path: utzoo!sq!lee
From: lee@sq.sq.com (Liam R. E. Quin)
Subject: Re: qsort
Message-ID: <1989Nov24.041216.17052@sq.sq.com>
Reply-To: lee@sq.com (Liam R. E. Quin)
Organization: Unixsys (UK) Ltd
References: <860@maytag.waterloo.edu>
Date: Fri, 24 Nov 89 04:12:16 GMT

In article <860@maytag.waterloo.edu> lhf@aries5 (Luiz H de Figueiredo) writes:
> My question is:
>	Does qsort have to implement quicksort?
Well, it would certainly be helpful if it did!  Otherwise how would even
begin to guess the complexity of one's programs?

> My point is that the *name* qsort is historical but qsort can actually be
> very smart, eg. switching to insertion for small segments and/or pre-scan the
> file (array) to avoid quadratic behaviour for sorted data.
Prescanning the array adds O(n) to the sort, slowing it down unacceptably.
It also adds disastrous paging behaviour for large arrays!
It is too late for insertaion sort, since the array is sorted in place, and
is already filled by the time qsort is called.
But 4.3BSD qsort() does in fact switch to a different algorithm for
short arrays, reducing the depth of recursion slightly.  There is also some
minimal effort at avoiding the worst-case behaviour, as I recall.
That qsort() routine is on the tape of publicly available files from the
4.3 Tahoe release.
THe point is (I think) that it is *at least* as fast as QuickSort, so
you don't need to worry about that aspect.
The improved worst-case and typical-case behaviour is a further incentive
to use it as far as I am concerned, although I don't know if the same
changes have mede it into System V.

> 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.
As I said in mail to soneone else today, if you save an average of one
whole second in runtime of the sort routine, at the cost of one hour's
programming, it takes 3,600 runs of the program before you even start to
break even.  And the extra cost of maintaining and debugggging your code
may make it worse.
If you save a millisecond, it takes 3,600,000 calls to LuizSort() before
you start to win.  And if your routine has to be ported....
But if you can save an hour, then do it.

First make it work, then make it fast.  [Brian Kernighan?  from ``Elements
of Programming Style''?  Sorry, I forget which Bible I am quoting!]

So I agree strongly -- use qsort.

Sorry to bring this up on comp.lang.c -- there seem to have been a lot
of "how do I sort" questions of late, though, so I thought it might
be worth while repeating.

Lee
-- 
Liam R. Quin, Unixsys (UK) Ltd [note: not an employee of "sq" - a visitor!]
lee@sq.com (Whilst visiting Canada from England)
People caught shopping are warned that they will be fined by an amount not
exceeding the total value of their purchases, plus sales tax.