Comb sort en Python — bubble con peine para sacar a las tortugas (con animación)

Comb sort es lo que pasa cuando alguien mira bubble sort y dice “y si en vez de comparar solo vecinos, comparamos elementos separados por un peine de dientes largos que va menguando?”. Resultado: un algoritmo que rompe el O(n²) puro de bubble y se queda en algo entre Θ(n log n) y O(n²) en la práctica, dependiendo del factor de reducción del gap.

La idea es prima de shell sort, pero aplicada a bubble en lugar de a insertion. Lo inventaron Włodzimierz Dobosiewicz en 1980 y, de forma independiente, Stephen Lacey y Richard Box en 1991.

Como cocktail sort, su razón de ser es resolver las “tortugas” de bubble: valores pequeños atrapados cerca del final. Pero comb las saca mucho más rápido que cocktail, porque los empuja con saltos grandes desde la primera pasada.

Esta entrada cubre el algoritmo en serio: cómo funciona paso a paso, implementación en Python, JavaScript y Java, su complejidad y comparativa.

Si quieres el panorama de los 14 algoritmos del clúster: Algoritmos de ordenación en Python — los 14 explicados.

Comb sort en una frase

Aplicar bubble sort comparando elementos separados por un “gap” (peine), no vecinos. Reducir el gap dividiéndolo por 1.3 cada pasada. Cuando el gap vale 1, es bubble sort normal — pero sobre una lista que ya está casi ordenada.

Animación sobre 12 valores:

Antes de seguir: qué quieren decir O, Θ y Ω

En las tablas verás los tres símbolos. Idea rápida:

• O(n²) — cota superior (peor caso).
• Ω(n log n) — cota inferior (mejor caso) con el factor de reducción 1.3.
• Θ(n²/2^p) — caso típico (donde p = nº de pasadas; con el factor 1.3 termina cerca de Θ(n log n) en la práctica).

Comb sort, como shell, tiene complejidad que depende del factor de reducción. Con 1.3 (el famoso “shrink factor” óptimo) se comporta razonablemente bien. Con un factor mayor degenera a Θ(n²). Explicación más larga en el pilar del clúster.

Cómo funciona — traza paso a paso

Ordenamos [8, 4, 1, 56, 3, -44, 23, -6, 28, 0] (n=10).

Gap inicial = n = 10. Lo dividimos por 1.3 al empezar → gap = 7.

Pasada con gap=7:

Posición:  0   1   2   3   4   5    6   7   8   9
Lista:     8   4   1   56  3   -44  23  -6  28  0
           ↓                            ↓
           (0 y 7)  8 vs -6  → intercambia → [-6, 4, 1, 56, 3, -44, 23, 8, 28, 0]
               ↓                                ↓
               (1 y 8) 4 vs 28 → ya bien
                   ↓                                ↓
                   (2 y 9) 1 vs 0 → intercambia → [-6, 4, 0, 56, 3, -44, 23, 8, 28, 1]

Reducimos: gap = 7 / 1.3 ≈ 5.

Pasada con gap=5:

[-6, 4, 0, 56, 3, -44, 23, 8, 28, 1]
 ↓                  ↓
 (0 y 5) -6 vs -44 → intercambia → [-44, 4, 0, 56, 3, -6, 23, 8, 28, 1]
     ↓                  ↓
     (1 y 6) 4 vs 23 → ya bien
         ↓                  ↓
         (2 y 7) 0 vs 8 → ya bien
             ↓                  ↓
             (3 y 8) 56 vs 28 → intercambia → [-44, 4, 0, 28, 3, -6, 23, 8, 56, 1]
                 ↓                  ↓
                 (4 y 9) 3 vs 1 → intercambia → [-44, 4, 0, 28, 1, -6, 23, 8, 56, 3]

Reducimos: gap = 5 / 1.3 ≈ 3.

Continuamos pasada con gap=3, luego gap=2, luego gap=1 (bubble normal sobre lista casi ordenada → muy poca corrección).

La idea clave: con gap grande, los elementos viajan rápido a su zona. Cuando el gap se reduce a 1, ya casi no quedan elementos descolocados — y bubble en una lista casi ordenada es rapidísimo.

Implementación en Python

def ordenar(lista: list[int]) -> list[int]:
    n = len(lista)
    gap = n
    cambio = True
    while gap > 1 or cambio:
        gap = max(1, int(gap / 1.3))
        cambio = False
        for i in range(n - gap):
            if lista[i] > lista[i + gap]:
                lista[i], lista[i + gap] = lista[i + gap], lista[i]
                cambio = True
    return lista


if __name__ == "__main__":
    print(ordenar([8, 4, 1, 56, 3, -44, 23, -6, 28, 0]))
    # [-44, -6, 0, 1, 3, 4, 8, 23, 28, 56]

Detalles:

1. El factor 1.3 es mágico. Empíricamente es el mejor: con factores mayores degenera, con menores hace demasiadas pasadas. Lacey y Box lo descubrieron y se ha mantenido como el estándar.
2. max(1, int(gap / 1.3)) evita que el gap caiga a 0. Asegura una pasada final con gap=1.
3. while gap > 1 or cambio: termina cuando el gap es 1 y la última pasada no hizo cambios. Garantiza que la lista quedó ordenada.

En entrevistas, mencionar que el factor 1.3 es empírico y no demostrado teóricamente como óptimo suma puntos. Es la clase de detalle que demuestra que sabes lo que dices.

Implementación en JavaScript

function ordenar(lista) {
  const n = lista.length;
  let gap = n;
  let cambio = true;
  while (gap > 1 || cambio) {
    gap = Math.max(1, Math.floor(gap / 1.3));
    cambio = false;
    for (let i = 0; i + gap < n; i++) {
      if (lista[i] > lista[i + gap]) {
        [lista[i], lista[i + gap]] = [lista[i + gap], lista[i]];
        cambio = true;
      }
    }
  }
  return lista;
}

Implementación en Java

public static void ordenar(int[] lista) {
    int n = lista.length;
    int gap = n;
    boolean cambio = true;
    while (gap > 1 || cambio) {
        gap = Math.max(1, (int)(gap / 1.3));
        cambio = false;
        for (int i = 0; i + gap < n; i++) {
            if (lista[i] > lista[i + gap]) {
                int tmp = lista[i]; lista[i] = lista[i + gap]; lista[i + gap] = tmp;
                cambio = true;
            }
        }
    }
}

Complejidad — depende del factor

Métrica	Mejor caso	Caso medio	Peor caso
Tiempo	Ω(n log n)	Θ(n²/2^p)	O(n²)
Memoria	O(1)	O(1)	O(1)
Estable	No	No	No

Por qué el caso medio se acerca a Θ(n log n): cada pasada reduce el gap por 1.3, así que con n elementos haces ~log₁.₃(n) pasadas. Si cada pasada hace ~n comparaciones, total ≈ n · log n. Pero no es prueba formal — comb sort tiene complejidad media empírica buena pero la teoría es difusa.

Por qué NO es estable. El intercambio salta sobre elementos intermedios — dos valores iguales pueden cambiar su orden relativo.

Ver en acción — comb sort sobre 10 listas fijas

Todo el clúster usa las mismas 10 listas fijas (n=15):

#	Nombre	Qué es
1	ordenada	1, 2, 3, ..., 15
2	inversa	15, 14, ..., 1
3	casi_ordenada	1..15 con un par de swaps
4	muy_desordenada	Patrón min-max alternado
5	duplicados	Enteros del rango [1..5] repetidos
6-10	aleatoria_s1 .. aleatoria_s5	5 permutaciones aleatorias deterministas

Aplicamos comb sort:

from sortlab import bench_estandar, formato_tabla
print(formato_tabla(bench_estandar("comb", n=15)))

Salida real:

Lista            Comp.  Interc.  Escr.  Tiempo (ms)   Caso  Θ observada
---------------  -----  -------  -----  -----------  -----  -----------
ordenada         70           0      0        0.005  Medio   Θ(n log n)
inversa          84          11     22        0.007  Medio        Θ(n²)
casi_ordenada    84          13     26        0.007  Medio        Θ(n²)
muy_desordenada  98          15     30        0.008   Peor        Θ(n²)
duplicados       70           9     18        0.006  Medio   Θ(n log n)
aleatoria_s1     84          20     40        0.008  Medio        Θ(n²)
aleatoria_s2     84          16     32        0.007  Medio        Θ(n²)
aleatoria_s3     84          18     36        0.008  Medio        Θ(n²)
aleatoria_s4     84          17     34        0.008  Medio        Θ(n²)
aleatoria_s5     84          14     28        0.007  Medio        Θ(n²)

Lectura de la tabla:

• Comparaciones entre 70 y 98 — rango muy estrecho. Comb es insensible a la forma de la entrada (ventaja sobre bubble).
• Lo importante: los INTERCAMBIOS. En inversa, comb hace 11 intercambios; bubble haría 105. Comb los reduce casi 10 veces porque los grandes saltos colocan rápido los extremos.
• ordenada → 70 comparaciones, 0 intercambios. Comb hace varias pasadas para confirmar que no hay desorden (no se “rinde” en una pasada como bubble con su booleano).
• Comparado con bubble sobre inversa (cifras reales):

Algoritmo	Comparaciones	Intercambios
Bubble	105	105
Comb	84	11

Comb hace 80% de las comparaciones de bubble pero solo el 10% de los intercambios. Esa es su ventaja real.

Reproducirlo sin instalar nada

sortlab vive privada en el Python profesional: medir, optimizar y escalar. Versión instrumentada inline:

def comb_medido(lista_original: list[int]) -> dict:
    arr = list(lista_original)
    comparaciones = 0
    intercambios = 0
    n = len(arr)
    gap = n
    cambio = True
    while gap > 1 or cambio:
        gap = max(1, int(gap / 1.3))
        cambio = False
        for i in range(n - gap):
            comparaciones += 1
            if arr[i] > arr[i + gap]:
                arr[i], arr[i + gap] = arr[i + gap], arr[i]
                intercambios += 1
                cambio = True
    return {"ordenada": arr, "comparaciones": comparaciones, "intercambios": intercambios}


listas = {
    "ordenada":         list(range(1, 16)),
    "inversa":          list(range(15, 0, -1)),
    "casi_ordenada":    [1, 11, 3, 4, 5, 6, 7, 8, 9, 10, 2, 12, 13, 14, 15],
    "muy_desordenada":  [1, 15, 2, 14, 3, 13, 4, 12, 5, 11, 6, 10, 7, 9, 8],
    "duplicados":       [1, 1, 3, 2, 2, 2, 1, 5, 1, 5, 4, 1, 1, 1, 2],
}
for nombre, lista in listas.items():
    r = comb_medido(lista)
    print(f"{nombre:<16}  comp={r['comparaciones']:>3}  swap={r['intercambios']:>3}")

Cuándo usar comb sort

Sí:

• Cuando ya tienes bubble en tu código y quieres mejorarlo sin reescribirlo. Cambiar 2 líneas para añadir el gap es trivial y duplica el rendimiento medio.
• Listas pequeñas y medianas donde el overhead de quick/merge no compensa.
• Educación: enseña la misma idea que shell aplicada a bubble. Buena clase magistral.

No:

• Producción seria con listas grandes. Sigue siendo O(n²) en el peor caso. Quicksort/merge/heap ganan.
• Cuando necesitas estabilidad. Comb no es estable.

Comparativa rápida

Algoritmo	Mejor	Peor	Memoria	Estable	Idea base
Bubble	Ω(n)	O(n²)	O(1)	Sí	Vecinos
Cocktail	Ω(n)	O(n²)	O(1)	Sí	Vecinos en zigzag
Comb	Ω(n log n)	O(n²)	O(1)	No	Vecinos + gap variable
Shell	Ω(n log n)	O(n²)	O(1)	No	Insertion + gap variable

El paralelismo es bonito: shell es a insertion lo que comb es a bubble. Misma idea (saltos + reducción) aplicada a dos algoritmos diferentes. Y ambas mejoran significativamente al original sin cambiar la complejidad teórica del peor caso.

Mitos que circulan sobre comb sort

• “Comb sort es O(n log n).” Es aproximadamente Θ(n log n) en el caso medio, pero en el peor caso sigue siendo O(n²) — depende del factor de gap.
• “El factor 1.3 es matemáticamente óptimo.” Es empíricamente el mejor entre los probados, pero no hay prueba formal de que sea óptimo absoluto.
• “Comb sort es estable.” No lo es. Los saltos entre posiciones lejanas pueden separar elementos iguales.

¿Y en la stdlib de Python?

No. Python no incluye comb sort. Si quieres usarlo, son ~10 líneas.

Trivia algorítmica

Lacey y Box publicaron comb sort en Byte Magazine en 1991, presentándolo como “una mejora dramática de bubble sort”. El factor 1.3 lo descubrieron empíricamente: probaron muchos factores y midieron. Es una de las pocas constantes en algoritmos que se eligió por experimento, no por teoría matemática.

FAQ rápida

¿Es lo mismo que shell sort?
La idea de “gap variable” es la misma, pero comb se aplica a bubble (compara vecinos por gap e intercambia) y shell se aplica a insertion (inserta cada elemento en su sitio dentro de su subsecuencia). Resultados parecidos, mecánica distinta.

¿Es estable?
No.

¿Por qué 1.3 y no otro factor?
Empíricamente es el mejor para minimizar pasadas + comparaciones. Lacey y Box lo encontraron por benchmarks.

¿Qué es el “rabbit”?
Bubble tiene “tortugas” (valores pequeños atrapados al final). También tiene “conejos” (valores grandes cerca del principio que ya viajan rápido). Comb resuelve a las tortugas; los conejos no eran problema.

En resumen

Comb sort es bubble sort con un peine: comparas elementos separados por un gap que va menguando. La idea es prima de shell sort, pero aplicada a bubble en lugar de insertion. Saca a las “tortugas” rápido, mejora el rendimiento medio por una constante grande, y sigue siendo simple. Pedagógicamente brillante y, en la práctica, una mejora trivial de bubble con dos líneas de cambio.

Si quieres aprender a detectar mejoras simples que aceleran tu código sin reescribirlo entero —no solo a recitar algoritmos— ese es el camino del curso de El Pythonista.