home combSort

-----

.tHE .sIRIUS .cYBERNETICS .cORPORATION


Well, this is a very small sorting routine I once discovered in a newsgroup, called Comb-Sort.
It's quite small in size and also quite fast, altough I really can't say why. It's basically a kind of bubble-sort with variable gap-size.
In some quick tests with GfA-Basic I discovered that it's nearly as fast as quicksort, but the advantages are obvious:


The only disadvantage is that you have to resize the gap with a division by 1.3 (yes, a fraction). But you can also use those wonderful fixed-point-workarounds like:
    

mulu    #65536*10/13,D0  
swap    D0
 « instead of »      

mulu    #10,D0  
divu    #13,D0


So, here is the algorithm in pseudo-code:
       

gap = arraysize
   
;the list is sorted if gapsize=1 and no swap occured
while gap>1 or switchflag==true:
   
    gap = gap * 10 / 13         ;resize gap
    if gap < 1:                 ;gap must be at least one
        gap = 1
   
    if gap==9 or gap==10:       ;take advantage of little speedup
        gap=11
   
    switchflag = false          ;no swap so far
   
    for g = 1 to arraysize-gap:
   
        if array[g]>array[g+gap]:   ;in wrong order?
   
            helper=array[g]         ;yes, so swap them
            array[g]=array[g+gap]
            array[g+gap]=helper
            switchflag=true         ;remember that we swapped

The original article said:
"the only known routines that can compete with ours in execution speed cannot compete in coding ease"
And I have to admit it's true...


A quick search on the web also provided this quote (so you know the source of this routine as well):
"The comb sort was first published by Richard Box and Stephen Lacey in the April 1991 issue of Byte magazine. They found that using a sequence for the gaps that decreased by a shrink factor of 1.3 gave the best results. Trial and error produced the refinement that an eventual gap size of 11, (rather than 9 or 10) gave a more efficient sequence of gaps below that point."




bresenham fast interpolation chunky2planar
codeTips .tSCc.


home -----

 
Lotek Style lotekstyle@tscc.de
SCY scy@tscc.de
dynaCore dynacore@tscc.de
RAY ray@tscc.de
Creature XL creature@tscc.de
 
 
Llama llama@tscc.de
Moondog moondog@tscc.de
Gizmo gizmo@tscc.de
Remo remo.williams@tscc.de


-----