Better qsort implementation

D'Arcy J.M. Cain darcy at druid.uucp
Sat Apr 14 00:51:19 AEST 1990

I wrote a program in C which has a section that sorts a large file.  It
tries to allocate enough space to load all the keys into memory and if
that fails it does the sort on disk.  On my Unix box I always have enough
room to load all the keys.  On the messy-Dos box I never have enough.  The
Dos box also has a much slower disk and no disk caching.  All of this led
me to expect the sort to go faster on the Unix box and that is the case but
I was unprepared for the actual extent of the difference.  The Dos machine
took 6 hours while the Unix took 9 seconds !!!!!

I thought there must be more to it so I did a few test and found that the
Unix qsort only had to do 141,096 compares while the Dos needed 548,698.
I guess the Turbo C implementation is slightly :-) less efficient than
the Unix one.

So now my question.  Is there a PD version of a quicksort routine which is
as good as the Unix version or better?  In fact if someone can point me
to a better routine than quicksort all the better.  I am using ESIX which
is an AT&T Sys5 3.2 port.  The data I am sorting is alpha-numeric keyed.

D'Arcy J.M. Cain (darcy at druid)     |   Government:
D'Arcy Cain Consulting             |   Organized crime with an attitude
West Hill, Ontario, Canada         |
(416) 281-6094                     |

More information about the Comp.lang.c mailing list