Newsgroups: comp.sys.amiga.programmer Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sdd.hp.com!elroy.jpl.nasa.gov!decwrl!pa.dec.com!bacchus!mwm From: mwm@pa.dec.com (Mike (My Watch Has Windows) Meyer) Subject: Re: Combsort algorithm In-Reply-To: 231b3678@fergvax.unl.edu's message of 7 May 91 17:32:56 GMT Message-ID: Sender: news@pa.dec.com (News) Organization: Missionaria Phonibalonica References: <1193@cbmger.UUCP> <1991May3.201243.7959@watdragon.waterloo.edu> <1991May6.155148.1201@zorch.SF-Bay.ORG> <231b3678.673637576@fergvax> Date: 8 May 91 18:25:12 Lines: 57 In article <231b3678.673637576@fergvax> 231b3678@fergvax.unl.edu (Phil Dietz) writes: In <1991May6.155148.1201@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: >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. I was VERY amazed at the comb-sorts results. I ran the test on my system, and you know what, comb-sort beat qsort by a heinous time! I sorted a list of ints (100000 of them). I used the comb-sort routine directly from the article, and I used qsort routine that comes with Lattice. sorting the same list of 100000 elements: qsort 165.3 secs comb 53.2 secs This either shows that the comb-sort is FAST, or the Lattice Qsort is SLOW! No, it shows what happens when you compare a general sort utility to one tailored for the problem at hand. Your comb-sort got to use a direct comparisons and assignments instead of a function calls. That makes each comparison and exchange an order of magnitude (or more) more expensive for SAS qsort than for your coomb-sort. A closer-to-fair comparison would be to write your own quicksort for sorting a fixed-size array of known object types. I cheated, and tweaked your comb-sort to call sortfunct for the comparison, and memcpy for the assignments, whicih should have roughly the same effect. I got: comb-sort of 100000 elements: 42.46 seconds qsort of 100000 elements: 27.12 seconds I.e. - the quicksort is roughly twice as fast for this case. Note: what I did - or even what I suggested doing - doesn't constitute a serious study of the problem. It just points out the flaws in what was presented earlier. In reality, I'll continue using qsort(), even though I can get faster results by handcoded routines. When a profiled run of the code shows that the serious delays are caused by the qsort, I'll change it to something faster, and chosen for the problem at hand. Meanwhile, I'm waiting to see what BSD is going to do with Bernsten's combinatorial sort, which sorts things in order(total_keysize). And there's a thing called "fusion sort" that might be the same thing in another guise....