Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!decwrl!pa.dec.com!bacchus!mwm
From: mwm@pa.dec.com (Mike (My Watch Has Windows) Meyer)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: Combsort algorithm
Message-ID: <MWM.91May17113450@raven.pa.dec.com>
Date: 17 May 91 18:34:50 GMT
References: <191d6f59.ARN12eb@pilhuhn.ka.sub.org>
	<1991May15.220144.27507@unislc.uucp>
Sender: news@pa.dec.com (News)
Organization: Missionaria Phonibalonica
Lines: 24
In-Reply-To: ttobler@unislc.uucp's message of Wed, 15 May 91 22:01:44 GM

In article <1991May15.220144.27507@unislc.uucp> ttobler@unislc.uucp (Trent Tobler) writes:
   > Which bucket-sort you can even achieve O(n)!
     ^^^ is this suppost to be 'With'?

   And anyway, who can afford the memory with a bucket sort on any generic
   data? (Isn't the bucket sort the one where for each element, an
   integer is calculated which has the property such that A<B for
   items A and B, f(A) < f(B) holds; and then to do the sort, you
   simply increment the count of C[f(X)], and then reconstructing the
   list based on C?)

Well, that's one form of bucket sort. For sorting generic data, it's
probably better to do a multi-pass bucket sort, where you sort on one
byte of the key on each pass. Net result is a sort that is O(keysize),
for the total size of the keys (it can't be expressed cleanly in terms
of the number of keys). With equal-size objects, this can be done in
place.

	<mike
--
Don't tell me how to live my life			Mike Meyer
Don't tell me what to do				mwm@pa.dec.com
Repression is always brought about			decwrl!mwm
by people with politics and attitudes like you.