Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!ira.uka.de!smurf!flatlin!pilhuhn!hwr From: hwr@pilhuhn.ka.sub.org (Heiko W.Rupp) Newsgroups: comp.sys.amiga.programmer Subject: Re: Combsort algorithm Message-ID: <191d6f59.ARN12eb@pilhuhn.ka.sub.org> Date: Thu, 09 May 91 18:17:29 GMT References: <1193@cbmger.UUCP> <1991May3.201243.7959@watdragon.waterloo.edu> <1991May6.155148.1201@zorch.SF-Bay.ORG> <231b3678.673637576@fergvax> Lines: 46 > In article mwm@pa.dec.com (Mike (My Watch Has Windows) Meyer) writes: > > > 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 > >[...] > > comb-sort of 100000 elements: 42.46 seconds > > qsort of 100000 elements: 27.12 seconds > > If you want to be even more closer-to-fair you wouldn't give results > for only sorting one amount of numbers. You should really show a > graph of how they work on 1000, 2000, 3000, 5000, 10000, 15000... (note > the logorithmic increase) elements. > > Of course, if you want to be the most accurate (by computer theory > standards) you wouldn't even run the program! You'd just figure the > O() of the function. ^^^^^^ Perhaps you know, that there is a computer-theory-theorey proof, that no comparision-based sorting algorithm can run faster than O(n log n) which is a lower bound for sorting. Which bucket-sort you can even achieve O(n)! For details on this subject see U.Manber : 'Introduction to Algorithms' (Addison-Wesley ISBN 0-201-12037-2) Chapter 6.4.6 and D.E.Knuth : 'The Art of computer programming - sorting and searching' (Addison-Wesley ISBN unknown) In the articles you will see, that Quicksort ist the fastest comparision- based sorting algorithm on the average, but it may take O(n*n) in the worst case. Heapsort on the other side is guaranteed to sort in O(n log n), but in the average case it is slower than Quicksort. Quicksort's running time depends on the input an on it's implementation. Hope that helps ... -Heiko -- Heiko W.Rupp, Gerwigstr.5, D-7500 Karlsruhe 1 | hwr@pilhuhn.ka.sub.org Tel: +49 7021 693642 (voice only) | uk85@dkauni2.bitnet All opinions expressed are my own, but sometimes I don't know what I say Gruesse -Heiko -- Heiko W.Rupp, Gerwigstr.5, D-7500 Karlsruhe 1 | hwr@pilhuhn.ka.sub.org Tel: +49 7021 693642 (voice only) | uk85@dkauni2.bitnet All opinions expressed are my own, but sometimes I don't know what I say