Talk:Sorting algorithms/Comb sort

Faulty Code

After discussion on AHK forum, and thoroughly checking the findings, I believe the published pseudocode is faulty, and so are the implementations that follow the pseudocode. I don't have the ability to check all languages, but these look suspicious to me: ActionScript, C#, Io, PL/I, PureBasic (2nd example), Python, Ruby, Tcl, TI-83 BASIC. I appologize for suspecting any code incorrectly, but I do have a point with python.

This example for Python:

...

x = [88, 18, 31, 44, 4, 0, 8, 81, 14, 78, 20, 76, 84, 33, 73, 75, 82, 5, 62, 70]
combsort(x)
print x

gives this incorrect output: (check the position of 62 und 70)

[0, 4, 5, 8, 14, 18, 20, 31, 33, 44, 70, 62, 73, 75, 76, 78, 81, 82, 84, 88]

I claim no credit for the discovery for myself, as my original code (for AutoHotkey) fell into the same trap, and got corrected by a fellow forum member.

--Wolf 13:44, 16 May 2010 (UTC)

PS: The pseudocode might be fixed by changing this:

        //update the gap value for a next comb. Below is an example
        gap := int(gap / 1.25)

to this:

        //update the gap value for a next comb. Below is an example
        if gap > 1
            gap := int(gap / 1.25)
        end if

--Wolf 14:08, 16 May 2010 (UTC)

After a most polite request from Wolf, I had a look at what might be an "authoritative" comb sort site from the US National Institute of Standards and Technology (NIST) which links to this java example implementation, which does indeed ensure that the gaps minimum value is 1 with this section of its code:

<lang java> gap = (int) ((float) gap / SHRINKFACTOR);

           switch (gap) {
           case 0: /* the smallest gap is 1 - bubble sort */
               gap = 1;
               break;</lang>

In short - Wolf is right: the pseudo-code is wrong. (The counter-example above does not lie). --Paddy3118 05:23, 27 May 2010 (UTC)

Correct the task and mark the examples as ENA? Someone should also make the relevant corrections at Wikipedia. --Michael Mol 12:48, 27 May 2010 (UTC)