Cocktail sort
11-12-2021
Ordenamiento de burbuja bidireccional
El ordenamiento de burbuja bidireccional es una mejora de la ordenación en burbujas. Se utiliza principalmente como herramienta educativa.
Intenta mitigar un defecto de la clasificación por burbujas: el problema de los conejos y las tortugas. Se trata de una situación en la que se coloca una burbuja pesada al final de la matriz. Mientras las burbujas ligeras (conejos) ascienden rápidamente, la burbuja pesada (tortuga) desciende sólo una posición por cada iteración.
Este algoritmo acelerará las tortugas cambiando de dirección en cada iteración. Así, con cada cambio de dirección, los “conejos” se convierten en “tortugas” y viceversa. Esto no sólo permite que los elementos más grandes migren rápidamente al final de la lista, sino que también permite que los elementos más pequeños migren más rápido al principio.
La siguiente animación muestra cómo funciona el algoritmo:
Trabajo práctico
El minijuego que se presenta a continuación permite intentar clasificar, en orden de peso creciente, 5 barriles, con una balanza Roberval para compararlos.
Distintas variantes
La versión más común de este algoritmo se compone de dos bucles anidados.
void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void shakersort(int vect[], int size) {
int step, current;
for (step = 1; step <= size / 2; step++)
{
for (current = step - 1; current < size - step; current++)
if (vect[current] > vect[current+1])
swap(&vect[current], &vect[current + 1]);
for (current = size - step - 1; current >= step; current--)
if (vect[current] < vect[current-1])
swap(&vect[current], &vect[current - 1]);
}
}
Pero prefiero una versión con un solo bucle y un cambio de dirección.
Rendimiento
El ordenamiento de burbuja bidireccional no es mucho más eficiente que el ordenamiento de burbuja convencional.
En el caso desfavorable, con un arreglo ordenado en orden inverso, realizará un número de intercambios de (n2 - n) / 2. Por ejemplo, para una lista de 10 elementos se necesitarán 45 comparaciones y 45 intercambios [ (102 - 10) / 2 ]. El número de comparaciones o de intercambios en el caso más desfavorable pertenece al orden O(n2).
En el caso óptimo, con un arreglo ya ordenado, realizará un número de comparaciones de (n - 1). El número de comparaciones en el caso más favorable pertenece al orden de O(n).
En el caso promedio realizará un número de comparaciones de (n2 - 2*n) / 4, sólo un poco mejor que el ordenamiento de burbuja convencional.
La animación siguiente permite comprobar, de forma empírica, esta evolución del número de operaciones en función del número de elementos a ordenar.
| Tamaños de datos | Comparaciones | Intercambios | Total |
|---|
Para tener una idea más concreta del rendimiento de este algoritmo, he aquí los tiempos que serían necesarios para ordenar la lista de habitantes de algunas grandes ciudades :
| Ciudad | Población | Duración estimada |
|---|---|---|
| Paimpol (Bretaña, Francia) | 7 172 | |
| Helsinki | 631 695 | |
| Denver | 705 576 | |
| Estocolmo | 975 551 | |
| Berlín | 3 520 031 | |
| Nairobi | 4 734 881 | |
| Barcelona | 5 407 264 | |
| Río | 6 718 000 | |
| Moscú | 12 655 050 | |
| Lagos | 22 829 561 | |
| Shanghai | 24 870 895 | |
| Seúl | 26 000 782 | |
| Manila | 28 644 207 | |
| Tokio | 42 796 714 |
