Comb sort

El factor de encogimiento tiene un gran efecto en la eficiencia del algoritmo comb sort. En el artículo original, los autores sugirieron 1,3 después de probar algunas listas aleatorias y encontrarlo generalmente el más efectivo. Un valor muy pequeño reduce la velocidad del algoritmo porque se deben hacer más comparaciones, mientras que un valor demasiado grande puede que no elimine suficientes tortugas para que sea práctico.

El texto describe una mejora del algoritmo comb sort usando el valor base ${\displaystyle 1/(1-{\frac {1}{e^{\varphi }}})\approx 1.247330950103979}$ como factor de encogimiento. También contiene una implementación en pseudocódigo con unas tablas de espacios predefinidos.

Con un factor de encogimiento alrededor de 1,3, sólo hay tres posibles maneras de que la lista de espacios acabe: (9, 6, 4, 3, 2, 1), (10, 7, 5, 3, 2, 1), o (11, 8, 6, 4, 3, 2, 1). Sólo el último de estos dos finales mata todas las tortugas antes de que el espacio se convierta en 1. Por lo tanto, se pueden hacer mejoras significativas en la velocidad si el espacio se establece en 11 siempre que sea 9 o 10. A esta variación se le llama Combsort11.

Si se usa cualquiera de la secuencias que comienza por 9 o 10, el paso final con un espacio de 1 es menos probable que haya ordenado los datos completamente, necesitando otro paso con un espacio de 1. Los datos están ordenados cuando no se hacen intercambios durante un paso con espacio = 1.

function combsort11(array input)
    gap:= input.size //inicializar tamaño de espacio
    
    loop until gap = 1 and swaps = 0
        //actualizar el valor del espacio para el siguiente rastreo
        if gap > 1
            gap:= gap / 1.3
            if gap = 10 or gap = 9
                gap:= 11
            end if
        end if
        

        i:= 0
        swaps:= 0 //véase ordenamiento de burbuja para una explicación
        //un único "rastreo" sobre la lista de entrada
        loop until i + gap >= array.size
            if array[i] > array[i+gap]
                swap (array[i], array[i+gap])
                swaps:= swaps + 1
            end if
            i:= i + 1
        end loop
    end loop
end function

• Ordenamiento de burbuja, un algoritmo generalmente más lento, es la base del algoritmo comb sort.
• Cocktail sort, un ordenamiento de burbuja bidireccional, es una variación del ordenamiento de burbuja que también trata el problema de las tortugas.

• Implementaciones del algoritmo en Wikibooks (inglés)
• Implementaciones del algoritmo en RosettaCode (inglés)