Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!apple!olivea!oliveb!veritas!amdcad!sun!quintus!pds
From: pds@quintus.UUCP (Peter Schachte)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: Combsort algorithm
Message-ID: <1521@quintus.UUCP>
Date: 10 May 91 22:18:25 GMT
References: <1193@cbmger.UUCP> <1991May3.201243.7959@watdragon.waterloo.edu> <1991May6.155148.1201@zorch.SF-Bay.ORG> <MWM.91May7111453@raven.pa.dec.com> <mjl.8698@alison.at>
Reply-To: pds@quintus.UUCP (Peter Schachte)
Organization: Quintus Computer Systems, Inc.
Lines: 16

In article <mjl.8698@alison.at> mjl@alison.at writes:
>  Following my docs, heapsort always does O(N ld N), while quicksort
>is N ld N (best), N^2/2 (worst case), and 1.4 N ld N (average).

There are lots of N log N sorts, so the constant factors start getting
important in choosing.  Also note that you need to consider both the
number of comparisons as well as the number of exchanges.  In fact, if
you sort an array of pointers to records, exchanges are pretty cheap.
And if your keys are strings rather than integers, comparisons are
much more expensive.  It's often more important to minimize the numer
of comparisons rather than the number of exchanges.

-- 
-Peter Schachte
pds@quintus.com
...!{uunet,sun}!quintus!pds