Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!cs.utexas.edu!sun-barr!apple!spies!zorch!xanthian From: xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) Newsgroups: comp.sys.amiga.programmer Subject: Re: Combsort algorithm Keywords: sorting, Combsort Message-ID: <1991May6.155148.1201@zorch.SF-Bay.ORG> Date: 6 May 91 15:51:48 GMT References: <1193@cbmger.UUCP> <1991May3.201243.7959@watdragon.waterloo.edu> Organization: SF-Bay Public-Access Unix Lines: 31 ccplumb@rose.waterloo.edu (Colin Plumb) writes: > I saw it briefly and was thrilled that BYTE had finally discovered > shellsort. If it beats heapsort, though, I may be wrong. How does it > work? Much like shell-sort, but instead of decreasing the span by a factor of 1.7 or so per loop, and then repeating each loop until no swaps are seen, the span is decreased by only 1.3 per loop, but each loop runs just once until the span one loop, which is run until no swaps occur. There seems also to be some special casing that a span of 9 or 10 is replaced by a span of 11 for reasons worth reading the article to puzzle out. I did the same about 1967, as I'm sure did thousands of others; the authors' biggest contribution is to run thorough tests to pick the "ideal" span divisor from loop to loop, and to detail performance. While it does (barely) beat heapsort, it takes almost twice as long as quicksort, so it is still not a choice you'd make except in a small sort, quick hack application. As a recent net posting showing quicksort in ML proved, there is nothing inherently complex about quicksort, our notation for programming just makes it look complex with a lanugage as weak as C. In such a procedural language, though, the comb-sort _looks_ much simpler, and is surely simpler to write, than either quicksort or heapsort. Kent, the man from xanth.