Cómo funciona
Cocktail Sort es Bubble Sort recorriendo en los dos sentidos. La pasada de ida, de
izquierda a derecha, arrastra el mayor de la zona sin ordenar hasta su extremo derecho. La de vuelta,
de derecha a izquierda, arrastra el menor hasta el extremo izquierdo. El array se va ordenando desde
los dos lados: dos muros que se cierran hasta encontrarse.
Resuelve el problema de las tortugas. En Bubble Sort, un número grande al principio
(una liebre) llega al final en una sola pasada, pero un número pequeño al final solo retrocede una
posición por pasada. Con la pasada de vuelta, la tortuga cruza el array de golpe.
Si una pasada entera no intercambia nada, lo que queda entre los muros ya está en orden y termina.
Cada pasada cuesta lo mismo que una de Bubble Sort, así que solo puede ahorrar pasadas: sigue siendo
O(n²) en el caso medio y en el peor.
Paso a paso con [3, 5, 6, 9, 8, 2]
- 01Pasada 1 → (posiciones 0 a 5): 3-5, 5-6 y 6-9 en orden. 9 > 8, intercambia; 9 > 2, intercambia →
[3, 5, 6, 8, 2, 9]. El 9 queda fijo a la derecha: fin = 4.
- 02Pasada 2 ← (posiciones 4 a 0): 8 > 2, 6 > 2, 5 > 2 y 3 > 2, cuatro intercambios seguidos →
[2, 3, 5, 6, 8, 9]. El 2 cruza el array en una sola vuelta: inicio = 1.
- 03Pasada 3 → (posiciones 1 a 4): 3-5, 5-6 y 6-8 en orden. Sin intercambios: termina.
- ΣTotal: 3 pasadas, 12 comparaciones y 6 intercambios. Con los mismos datos, Bubble Sort necesita 5 pasadas y 15 comparaciones, porque el 2 solo retrocede una posición en cada una. Los intercambios coinciden: los dos corrigen una vez cada par desordenado.
Frente a Bubble Sort
Hacen exactamente los mismos intercambios: uno por cada par de números desordenados.
La diferencia está en las comparaciones, que dependen del número de pasadas. Con datos aleatorios
Cocktail suele necesitar menos, aunque hay casos en los que necesita alguna más. Prueba «Tortuga al
final» en Datos para ver la mayor diferencia.
Complejidad
- Mejor caso
- O(n)
- Caso promedio
- O(n²)
- Peor caso
- O(n²)
- Espacio extra
- O(1)
- Estable
- Sí
- In situ
- Sí