Cocktail sort en Python — bubble sort bidireccional (con animación)

Cocktail sort (también conocido como shaker sort o bidirectional bubble sort) es una variante de bubble sort que recorre la lista en zigzag: una pasada de izquierda a derecha empujando el mayor al final, luego una de derecha a izquierda empujando el menor al principio. Cada doble-pasada ordena por los dos extremos a la vez.

¿Lo bueno? Resuelve un problema clásico de bubble: las “tortugas“, valores pequeños atrapados al final de la lista que tardan muchísimas pasadas en llegar al principio. Cocktail los rescata en la pasada de vuelta.

¿Lo malo? Sigue siendo O(n²) en el peor caso. Más rápido que bubble por una constante, pero no cambia la complejidad.

Esta entrada cubre el algoritmo en serio: cómo funciona paso a paso, implementación en Python, JavaScript y Java, su complejidad real y cuándo se sigue usando.

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

Cocktail sort en una frase

Recorre la lista comparando vecinos e intercambiando los descolocados, igual que bubble. Pero en la pasada par va de izquierda a derecha; en la pasada impar va de derecha a izquierda. Cada vuelta cubre los dos extremos.

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²) — “O grande”, cota superior (peor caso).
• Ω(n) — “Omega”, cota inferior (mejor caso).
• Θ(n²) — “Theta”, caso típico.

Cocktail sort es Ω(n) (lista ya ordenada → una pasada y termina), Θ(n²) (caso medio) y O(n²) (peor caso). Mismo Big-O que bubble, pero con constante mejor. Explicación más larga en el pilar del clúster.

Cómo funciona — traza paso a paso

Ordenamos [5, 1, 4, 2, 8, 0, 2] (n=7) con cocktail.

Pasada 1, izquierda → derecha (empuja el mayor al final):

[5, 1, 4, 2, 8, 0, 2]
 ↑   compara 5 y 1 → 1 < 5, intercambia → [1, 5, 4, 2, 8, 0, 2]
    ↑ compara 5 y 4 → 4 < 5, intercambia → [1, 4, 5, 2, 8, 0, 2]
       ↑ compara 5 y 2 → 2 < 5, intercambia → [1, 4, 2, 5, 8, 0, 2]
          ↑ compara 5 y 8 → ya bien
             ↑ compara 8 y 0 → 0 < 8, intercambia → [1, 4, 2, 5, 0, 8, 2]
                ↑ compara 8 y 2 → 2 < 8, intercambia → [1, 4, 2, 5, 0, 2, 8]

El 8 está en el final. No volveremos a tocarlo.

Pasada 1, derecha → izquierda (empuja el menor al principio):

[1, 4, 2, 5, 0, 2, 8]
              ↑ compara 0 y 2 → 0 < 2, intercambia → [1, 4, 2, 5, 0, 2, 8] (ya estaba)
              wait, compara 2 y 0... vamos en dirección inversa, comparar arr[i] con arr[i-1]:
           ↑ compara 5 y 0 → 0 < 5, intercambia → [1, 4, 2, 0, 5, 2, 8]
        ↑ compara 2 y 0 → 0 < 2, intercambia → [1, 4, 0, 2, 5, 2, 8]
     ↑ compara 4 y 0 → 0 < 4, intercambia → [1, 0, 4, 2, 5, 2, 8]
  ↑ compara 1 y 0 → 0 < 1, intercambia → [0, 1, 4, 2, 5, 2, 8]

El 0 está en el principio. No volveremos a tocarlo.

Después de UNA doble-pasada, hemos colocado el máximo (8) y el mínimo (0). En bubble solo habríamos colocado el máximo. Esa es la ganancia.

Repetimos con los índices [1..5] hasta que la lista esté ordenada. Total: 14 comparaciones (vs 21 para bubble en el mismo input).

Implementación en Python

def ordenar(lista: list[int]) -> list[int]:
    n = len(lista)
    izq, der = 0, n - 1
    intercambio = True
    while izq < der and intercambio:
        intercambio = False
        # Pasada hacia la derecha (empuja el mayor)
        for i in range(izq, der):
            if lista[i] > lista[i + 1]:
                lista[i], lista[i + 1] = lista[i + 1], lista[i]
                intercambio = True
        der -= 1
        # Pasada hacia la izquierda (empuja el menor)
        for i in range(der, izq, -1):
            if lista[i - 1] > lista[i]:
                lista[i - 1], lista[i] = lista[i], lista[i - 1]
                intercambio = True
        izq += 1
    return lista


if __name__ == "__main__":
    print(ordenar([5, 1, 4, 2, 8, 0, 2]))  # [0, 1, 2, 2, 4, 5, 8]

Detalles:

1. Las variables izq y der marcan los límites del tramo “que aún puede tener desorden”. Tras cada doble-pasada, el extremo derecho ya tiene el máximo en su sitio (decrementa der), y el izquierdo el mínimo (incrementa izq).
2. intercambio global por doble-pasada: si una doble-pasada termina sin ningún intercambio, la lista ya está ordenada y salimos antes. Es el truco del mejor caso Ω(n).
3. Es estable, igual que bubble: la condición > estricta no intercambia iguales.

Implementación en JavaScript

function ordenar(lista) {
  let izq = 0, der = lista.length - 1;
  let intercambio = true;
  while (izq < der && intercambio) {
    intercambio = false;
    for (let i = izq; i < der; i++) {
      if (lista[i] > lista[i + 1]) {
        [lista[i], lista[i + 1]] = [lista[i + 1], lista[i]];
        intercambio = true;
      }
    }
    der--;
    for (let i = der; i > izq; i--) {
      if (lista[i - 1] > lista[i]) {
        [lista[i - 1], lista[i]] = [lista[i], lista[i - 1]];
        intercambio = true;
      }
    }
    izq++;
  }
  return lista;
}

Implementación en Java

public static void ordenar(int[] lista) {
    int izq = 0, der = lista.length - 1;
    boolean intercambio = true;
    while (izq < der && intercambio) {
        intercambio = false;
        for (int i = izq; i < der; i++) {
            if (lista[i] > lista[i + 1]) {
                int tmp = lista[i]; lista[i] = lista[i + 1]; lista[i + 1] = tmp;
                intercambio = true;
            }
        }
        der--;
        for (int i = der; i > izq; i--) {
            if (lista[i - 1] > lista[i]) {
                int tmp = lista[i - 1]; lista[i - 1] = lista[i]; lista[i] = tmp;
                intercambio = true;
            }
        }
        izq++;
    }
}

Complejidad — la misma familia que bubble

Métrica	Mejor caso	Caso medio	Peor caso
Tiempo	Ω(n)	Θ(n²)	O(n²)
Memoria	O(1)	O(1)	O(1)
Estable	Sí	Sí	Sí

Mismo Big-O que bubble, pero con una constante mejor: cada doble-pasada coloca dos extremos en vez de uno, así que necesita la mitad de iteraciones para “asentar” la lista.

Por qué es estable. La condición > estricta nunca intercambia elementos iguales — ni en la pasada izquierda-derecha ni en la derecha-izquierda.

Ver en acción — cocktail 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 cocktail sort:

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

Salida real:

Lista            Comp.  Interc.  Escr.  Tiempo (ms)   Caso  Θ observada
---------------  -----  -------  -----  -----------  -----  -----------
ordenada         27           0      0        0.002  Mejor         Θ(n)
inversa          105        105    210        0.018   Peor        Θ(n²)
casi_ordenada    50          17     34        0.005  Medio   Θ(n log n)
muy_desordenada  102         49     98        0.012   Peor        Θ(n²)
duplicados       95          39     78        0.011   Peor        Θ(n²)
aleatoria_s1     95          62    124        0.013   Peor        Θ(n²)
aleatoria_s2     102         54    108        0.012   Peor        Θ(n²)
aleatoria_s3     102         62    124        0.013   Peor        Θ(n²)
aleatoria_s4     105         69    138        0.014   Peor        Θ(n²)
aleatoria_s5     84          50    100        0.010   Peor        Θ(n²)

Lectura de la tabla:

• ordenada → 27 comparaciones, Mejor, Θ(n). Una pasada izquierda-derecha confirma que no hay intercambios, y otra derecha-izquierda también: 27 ≈ 2·(n-1). Sale en una doble-pasada limpia.
• casi_ordenada → 50 comparaciones, Medio. Mejor que el bubble equivalente (95 comparaciones sobre la misma lista). La doble pasada llega antes a tocar los pocos elementos descolocados.
• inversa → 105 comparaciones, Peor. El peor caso de libro: cada par de vecinos está descolocado en ambas direcciones.
• Las aleatorias caen en Peor. Igual que bubble: si hay inversiones repartidas, cocktail también las paga todas.

Comparativa directa con bubble sobre las mismas listas:

Lista	Bubble (comp.)	Cocktail (comp.)
ordenada	14	27
casi_ordenada	95	50
inversa	105	105
aleatoria_s1	104	95

• En ordenada, bubble gana (14 vs 27): hace una sola pasada en vez de dos.
• En casi_ordenada, cocktail gana por casi la mitad (50 vs 95): la doble pasada llega rápido a los elementos descolocados.
• En inversa empatan (los dos hacen el máximo).
• En aleatorias, cocktail gana un poco (95 vs 104).

Es justo lo que predice la teoría: cocktail mejora a bubble por una constante, no cambia el orden de magnitud.

Reproducirlo sin instalar nada

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

def cocktail_medido(lista_original: list[int]) -> dict:
    arr = list(lista_original)
    comparaciones = 0
    intercambios = 0
    izq, der = 0, len(arr) - 1
    intercambio = True
    while izq < der and intercambio:
        intercambio = False
        for i in range(izq, der):
            comparaciones += 1
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                intercambios += 1
                intercambio = True
        der -= 1
        for i in range(der, izq, -1):
            comparaciones += 1
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]
                intercambios += 1
                intercambio = True
        izq += 1
    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 = cocktail_medido(lista)
    print(f"{nombre:<16}  comp={r['comparaciones']:>3}  swap={r['intercambios']:>3}")

Cuándo usar cocktail sort

Sí:

• Listas pequeñas con “tortugas”. Si tu lista tiende a tener valores pequeños al final (que tardarían muchísimo en llegar al principio con bubble), cocktail las rescata.
• Para enseñar la idea de “ir en zigzag” en una entrevista. Es un cambio mental simple sobre bubble que abre la conversación.

No:

• Producción seria. Sigue siendo O(n²). Cualquier O(n log n) lo bate.
• Listas grandes. Mismo problema que bubble: para n > 1.000 se vuelve doloroso.

Comparativa rápida

Algoritmo	Mejor	Peor	Memoria	Estable	Ventaja vs bubble
Bubble	Ω(n)	O(n²)	O(1)	Sí	—
Cocktail	Ω(n)	O(n²)	O(1)	Sí	Bidireccional: resuelve “tortugas”
Comb	Ω(n log n)	O(n²)	O(1)	No	Gap variable: rompe el orden cuadrático
Insertion	Ω(n)	O(n²)	O(1)	Sí	Mejor en casi todo el rango

El veredicto: cocktail mejora bubble por una constante, pero insertion lo bate a ambos en la práctica. Si tienes que elegir un O(n²) hoy, elige insertion.

Mitos que circulan sobre cocktail sort

• “Cocktail sort es lineal en el mejor caso, igual que bubble.” Cierto, pero su constante es peor (hace doble pasada antes de confirmar). Bubble es ligeramente más rápido en ordenada.
• “Es mejor que insertion.” No. Insertion sigue ganando en casi todos los escenarios reales.
• “Resuelve completamente el problema de las tortugas.” Lo mitiga, no lo elimina. Una “tortuga” muy alejada de su destino sigue necesitando varias pasadas.

¿Y en la stdlib de Python?

No. No hay cocktail sort en la stdlib. Si lo necesitas (rara vez), implementas las ~15 líneas.

Trivia algorítmica

Cocktail sort tiene varios nombres: shaker sort, bidirectional bubble sort, ripple sort, shuttle sort. La diversidad de nombres refleja que se ha “redescubierto” varias veces de forma independiente — es una idea tan simple que muchas personas llegan a ella sin haberla visto antes.

FAQ rápida

¿Es lo mismo que shaker sort?
Sí. “Cocktail sort” y “shaker sort” son nombres distintos para el mismo algoritmo.

¿Es estable?
Sí. Igual que bubble, no intercambia elementos iguales (> estricta).

¿Se puede combinar con la idea de comb sort (gaps)?
Sí. Existen variantes “cocktail con gaps” que combinan ambas ideas. Casi nadie las usa en producción.

¿Qué son “las tortugas”?
Valores pequeños atrapados cerca del final de la lista que en bubble sort tardan muchísimas pasadas en llegar al principio (porque bubble solo empuja “hacia adelante”). Cocktail las rescata con la pasada de vuelta.

En resumen

Cocktail sort es bubble sort haciendo zigzag. Su única ventaja real es resolver el problema de las “tortugas”, a costa de una constante peor en el mejor caso. Sigue siendo O(n²) y, en la práctica, insertion sort lo bate. Pero es conceptualmente bonito: enseña que “una pequeña modificación en cómo recorres” puede cambiar el rendimiento real sin tocar el algoritmo subyacente.

Si quieres aprender a detectar qué modificación simple acelera tu código —no solo a recitar algoritmos— ese es el camino del curso de El Pythonista.