Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!samsung!uunet!viusys!uxui!unislc!ttobler From: ttobler@unislc.uucp (Trent Tobler) Newsgroups: comp.sys.amiga.programmer Subject: Re: Combsort algorithm Message-ID: <1991Jun3.212323.5448@unislc.uucp> Date: 3 Jun 91 21:23:23 GMT References: Organization: unisys Lines: 35 From article , by andand@cia.docs.uu.se (Anders Andersson): >>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. There are actually sorts that beat quicksort on all data of a certain size of greater (they are quite complex, can't remember there names right now.) >>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 Well, combsort requires about twice the moves, and about the same number of compares, so if q-sort requires 15000 compares, and 5000 moves, then that is 20000 operations. The corresponding comb-sort would require 20000 compares, and would require 13000 moves, so that would mean 33000 operations; comb-sort is slower by about 1.65 times if compares and moves take about the same amount of time. Again, the main advantage (as I see it) of the comb-sort is that it's memory requirements are constant for ANY array. (true, quick-sort only requires ln(N)+C units of additional memory, which is not a lot) > -Anders Andersson (andand@cia.docs.uu.se) -- Trent Tobler - ttobler@csulx.weber.edu