comb sort

[Jimg]

I've been playing with the comb sort in masm32lib.

One question is about the value 1.29, or in the general literature "about 1.3".

Is there a reason we use the FPU rather than interger multiplication then shift for division?

1024/793 = 1.291...

1024/794 = 1.28967...

These seem to be very close, and since the algorithm say "about 1.3" I can't see a problem, unless there is some terrible oscillation that occurs if you use an exact power of two???

Any thoughts, anyone?

edit:  I had the fraction reversed in my first post.  Fixed.

[Jimg]

Well, there's definitely some kind of problem.

I replaced-

Code Select Expand

;    fild   Gap        ; load integer memory operand to divide
;    fdiv   CombSort_Const       ; divide number by 1.3
;    fistp  Gap       ; store result back in integer memory operand

    mov eax,Gap
    mul cc3         ; 794
    shr eax,10      ; /1024
    mov Gap,eax
and it crashes every time???

[Tedd]

Is the multiplication causing an overflow?

You'll probably want to reduce the numbers in any case - as long as they have the same ratio, the result is the same - divide them both by their GCD, though then you might not always get a nice power of 2 for the shift.

GCD(794,1024) = 2
So you can try 397/512 instead, which will at least reduce the chance of overflow.

[hutch--]

Jim,

From memory it has to do with the rounding direction of each result. The "1.3" figure is something you tweak manually on the basis of experimentation across enough cases. If you have time to play with it, a double ender (alternate processing direction) reduces the problem of "turtles" (values at the wrong end of the scale).

I found that once the gap had closed to one (1) it was better to shift to an insertion sort than continue with what had become a bubble lost.

[Jimg]

From memory it has to do with the rounding direction of each result. ...

You're right.  I changed the code to round and it seems to work correctly-

Code Select Expand


    mov eax,Gap
    mul cc3         ; 99
    shr eax,7     ; /128    =  1.29292929...
    adc eax,0
    mov Gap,eax

I found that using a fdiv takes 30 cycles, a fmul of 1/1.29 takes 14 cycles, and the interger routine takes 5 cycles.
upon further testing, I found that the division was done only 66 times on a 1 million size sample, so the whole this is meaningless in the real world, but I will probably multiply rather then divide:).

I found that once the gap had closed to one (1) it was better to shift to an insertion sort than continue with what had become a bubble lost.

isn't this what a shell sort is?  I'll have to think about this.  Also, would a comb11 sort have any effect on this?

I choose the comb sort because it seemed to be the fastest of the sorts without any listed failure conditions and at the same time was small.  I'm trying to keep my grid control small and if you sort a million records, the rest of the process of moving the records will take much longer than the actual sorting so I didn't see any reason to go to the more complicated sorts.

[hutch--]

Jim,

For cleaning up the tail of a number of different types of sorts which are almost ordered, an insertion sort has the legs, certainly over a bubble sort in the same context. If you have a look at the string sorts in the masm32 library, most of the types are there and the ones I used for the main hybrid sort is a mix of quick, comb and insertion sorts. On random data a quick sort has the legs, if the data is already highly ordered the quick sort exceeds a preset recursion depth and collapses back to a comb/insertion sort.

The comb sort is itself a hybrid that is double ended, like a cocktail shaker sort but on a comb sort rather than a bubble sort. I could never see the difference in timing from coding a comb11 variant so I never used it.