Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!wuarchive!uunet!viusys!uxui!unislc!ttobler From: ttobler@unislc.uucp (Trent Tobler) Newsgroups: comp.sys.amiga.programmer Subject: Re: Combsort algorithm Message-ID: <1991May15.220144.27507@unislc.uucp> Date: 15 May 91 22:01:44 GMT References: <191d6f59.ARN12eb@pilhuhn.ka.sub.org> Organization: unisys Lines: 95 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. > 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 > 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. > 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. > Quicksort also uses additional memory. As N gets larger, the amount of memory above that contained in the array to sort grows by ln(N). Heapsort and combsort are both iteritive sorts, which means they use a constant amount of memory for any N. I have an algorithem based on the merge sort that runs about the same as quick sort on random lists, and runs even faster on near-sorted lists. It's problem is that its memory requirements grow by N/2. 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. Here is a table I constructed showing various sort statistics: Random Sorted Backward-Sorted 10 100 1000 10 100 1000 10 100 1000 bubble-sort compares 45 4872 499455 9 99 999 45 4950 499500 moves 78 7413 722256 0 0 0 135 14850 1498446 comb-sort compares 32 1096 19706 32 1096 19706 32 1096 19706 moves 30 801 12612 0 0 0 21 348 4596 heap-sort compares 39 1030 16878 41 1081 17570 35 944 15966 moves 62 1041 13920 74 1134 14677 53 910 12314 m-sort compares 29 603 9403 15 316 4932 28 455 6047 moves 34 777 12942 0 0 0 49 988 14887 quick-sort compares 35 861 14878 45 4950 499500 50 5000 500000 moves 24 365 5066 18 198 1998 23 248 2498 shell-sort compares 32 704 13985 15 342 5457 21 500 8541 moves 52 1089 19883 30 684 10914 43 914 14825 The algorithems used were bubble: compare neighbors, swap if out of order. comb: described in Byte, April 1991 heap: vanilla heap sort m-sort: 1) divide list in half. 2) If size of either half > 2, recursively sort it. 3) merge sort each half (they are each in order because of (2)) quick: vanilla quicksort shell-sort: 3n+1 shell sort --- Trent Tobler - ttobler@csulx.weber.edu