Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!mintaka!bloom-beacon!eru!hagbard!sunic!kuling!cia.docs.uu.se!andand From: andand@cia.docs.uu.se (Anders Andersson) Newsgroups: comp.sys.amiga.programmer Subject: Re: Combsort algorithm Message-ID: Date: 31 May 91 16:29:57 GMT References: <191d6f59.ARN12eb@pilhuhn.ka.sub.org> <1991May15.220144.27507@unislc.uucp> Sender: news@kuling.UUCP Lines: 65 In <1991May15.220144.27507@unislc.uucp> ttobler@unislc.uucp (Trent Tobler) writes: >From article <191d6f59.ARN12eb@pilhuhn.ka.sub.org>, by hwr@pilhuhn.ka.sub.org (Heiko W.Rupp): >> >>> 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. >That is correct. He was saying to calculate the time function of the comb >sort compared to the quick sort. I believe the article stated that >the comb-sort algorithem appeared to be an O(n*ln n) sort. In other >words, as more elements are sorted, the ratio of time(quicksort)/time(combsort) >remains constant. Yes, I made a quick calculation that suggested that quicksort is 1.9 times faster. I tried to tell the world (or rather this newsgroup) but my message bounced. >> 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 then to do the sort, you simply increment the count of C[f(X)], and then > reconstructing the list based on C?) I'm not sure what bucket sort is, but radix sort is O(n) and it 'only' requires twice the memory (i.e. it needs a extra copy of the data). In a general application, you only sort pointers to data objects, so this isn't too bad. >> >> 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. >No, there are sorts which are faster. It all depends on what data you are sorting. Quicksort usually beets other sorts hands down in tests, mostly because it has a extremly short inner loop. This is a great advantage when sorting an array of integers or something, but not equally important in practice when each compare is associated with some overhead. [stuff deleted] >Of the sorts that I have tested, Quicksort tends to minimize the number of >moves on elements, but requires. Combsort did about twice the number of >moves as quicksort, and about the same number of compares. The m-sort I ^^^^^^^^^^^^^^^^^^^^^^^ >tested tended to minimize the number of comparisions, about 50% of that >quicksort required, but required 100% more moves. That's strange. Acording to my sources on quicksort and my own calculations of combsort, combsort should require 1.9 times as many compares. I might have missed something, but I can't imagine what. I should be able to count my way through nested loops... [stuff deleted] -Anders Andersson (andand@cia.docs.uu.se)