Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!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: Date: 15 Jun 91 20:51:00 GMT References: <8235@oasys.dt.navy.mil> <1991Jun13.175106.6902@unislc.uucp> <8454@oasys.dt.navy.mil> Sender: news@pa.dec.com (News) Organization: Missionaria Phonibalonica Lines: 43 In-Reply-To: tdsmith@oasys.dt.navy.mil's message of 14 Jun 91 15:31:57 GMT In article <8454@oasys.dt.navy.mil> tdsmith@oasys.dt.navy.mil (Timothy Smith) writes: The problem as I see it is that the bucket range has to be defined ahead of time. For reccuring problems this is fine, since m can be fixed. But for arbitrary problems it is not so clear. Yup, but there's a way around that. Choose some convenient size chunk, and combsort the high-order chunk of that size in each key. You've just partitioned the elements so that each element is in the partition it will be in when correctly sorted. Sort each bucket by the second chunk in the keys, producing a second level of buckets. Continue down the keys until either the buckets are singleton sets, or you run out of key (at which time all the keys in any bucket will be equal). The net result is that you've looked at each chunk a fixed number of times (once if you do it BFI, a few more if you finesse it). For real numbers m is infinite. I conclude combsort is not a general purpose sorting algorithm, just a special case integer sort over a finite set of input possibilities. Well, the above outlines a variant of combsort that applies to arbitrary keys. It's generally known as a "radix sort". For most computers (like an Amiga), "bytes" are the obvious convenient size chunk. That's what the implementation I've got uses. IN THEORY combsort is O(n), but theory sometimes has little relation to practicality. In theory, a radix sort is O(c), where c is the number of chunks. A combsort is a radixsort where c is the key size. This isn't practical for all keys. However, choosing a practical chunk size is always possible, and the resulting implementation works. - There are no general purpose sorts which do better than O(n*logn). False. See the above. It's a general purpose algorithm, and it's always better (in the theoretical sense) than O(n*logn).