Clasificación de coctelera , [1] también conocida como clasificación de burbujas bidireccional , [2] clasificación de cóctel , clasificación de coctelera (que también puede referirse a una variante de clasificación de selección ), clasificación de ondulación , clasificación aleatoria , [3] o clasificación de lanzadera , es una extensión del tipo de burbuja . El algoritmo amplía la clasificación de burbujas operando en dos direcciones. Si bien mejora la clasificación de burbujas al mover elementos más rápidamente al principio de la lista , solo proporciona mejoras marginales en el rendimiento.
Como la mayoría de las variantes del tipo de burbujas, el tipo de coctelera se utiliza principalmente como herramienta educativa. Las bibliotecas de clasificación integradas en lenguajes de programación populares como Python y Java utilizan algoritmos de mayor rendimiento, como quicksort , merge sort o timsort . [4] [5]
La forma más sencilla recorre toda la lista cada vez:
procedimiento cocktailShakerSort(A : lista de elementos ordenables) se hace intercambiado := falso para cada i en 0 hasta longitud(A) − 1 haga: si A[i] > A[i + 1] entonces // prueba si los dos elementos están en el orden incorrecto swap(A[i], A[i + 1]) // deja que los dos elementos cambien de lugar intercambiado := verdadero end if end for if not swapped entonces // podemos salir del bucle externo aquí si no se produjeron intercambios. romper el bucle do- while si intercambiado := falso para cada i en longitud (A) − 1 a 0 haga: si A[i] > A[i + 1] entonces intercambiar(A[i], A[i + 1]) intercambiado := verdadero end if end for while swapped // si no se han intercambiado elementos, entonces la lista está ordenada fin del procedimiento
El primer paso hacia la derecha desplazará el elemento más grande a su lugar correcto al final, y el siguiente paso hacia la izquierda desplazará el elemento más pequeño a su lugar correcto al principio. La segunda pasada completa desplazará el segundo elemento más grande y el segundo más pequeño a sus lugares correctos, y así sucesivamente. Después de pasar i , el primer elemento i y el último i de la lista están en sus posiciones correctas y no es necesario verificarlos. Al acortar la parte de la lista que se ordena cada vez, el número de operaciones se puede reducir a la mitad (ver clasificación por burbujas ).
Este es un ejemplo del algoritmo en MATLAB/OCTAVE con la optimización de recordar el último índice de intercambio y actualizar los límites.
función A = cocktailShakerSort ( A ) % `beginIdx` y `endIdx` marcan el primer y último índice para verificar beginIdx = 1 ; endIdx = longitud ( A ) - 1 ; mientras que beginIdx <= endIdx newBeginIdx = endIdx ; nuevoEndIdx = comenzarIdx ; para ii = comenzarIdx : endIdx si A ( ii ) > A ( ii + 1 ) [ A ( ii + 1 ), A ( ii )] = trato ( A ( ii ), A ( ii + 1 )); nuevoEndIdx = ii ; fin fin % disminuye `endIdx` porque los elementos después de `newEndIdx` están en el orden correcto endIdx = newEndIdx - 1 ; para ii = endIdx : - 1 : comenzarIdx si A ( ii ) > A ( ii + 1 ) [ A ( ii + 1 ), A ( ii )] = trato ( A ( ii ), A ( ii + 1 )); nuevoBeginIdx = ii ; end end % aumenta `beginIdx` porque los elementos antes de `newBeginIdx` están en el orden correcto beginIdx = newBeginIdx + 1 ; fin fin El tipo de coctelera es una ligera variación del tipo de burbuja . [1] Se diferencia en que en lugar de pasar repetidamente por la lista de abajo hacia arriba, pasa alternativamente de abajo hacia arriba y luego de arriba hacia abajo. Puede lograr un rendimiento ligeramente mejor que una clasificación de burbujas estándar. La razón de esto es que la clasificación de burbujas solo pasa por la lista en una dirección y, por lo tanto, solo puede mover elementos hacia atrás un paso en cada iteración.
Un ejemplo de una lista que demuestra este punto es la lista (2,3,4,5,1), que solo necesitaría pasar por una pasada de clasificación cóctel para ser ordenada, pero si se usara una clasificación de burbuja ascendente se necesitarían cuatro pasa. Sin embargo, una pasada de clasificación de cócteles debe contarse como dos pasadas de clasificación de burbujas. Normalmente, la clasificación de cócteles es menos de dos veces más rápida que la clasificación de burbujas.
Otra optimización puede ser que el algoritmo recuerde dónde se realizó el último intercambio real. En la próxima iteración, no habrá intercambios más allá de este límite y el algoritmo tiene pases más cortos. A medida que la clasificación de la coctelera es bidireccional, el rango de posibles cambios, que es el rango que se va a probar, se reducirá por pasada, reduciendo así ligeramente el tiempo total de funcionamiento.
La complejidad de la clasificación de la coctelera en notación O grande es tanto para el peor de los casos como para el caso promedio, pero se acerca más a si la lista está ordenada en su mayor parte antes de aplicar el algoritmo de clasificación. Por ejemplo, si cada elemento está en una posición que difiere como máximo en k (k ≥ 1) de la posición en la que va a terminar, la complejidad de la clasificación de la coctelera se vuelve
El tipo de coctelera también se analiza brevemente en el libro The Art of Computer Programming , junto con refinamientos similares del tipo de burbuja. En conclusión, Knuth afirma sobre la clasificación de burbujas y sus mejoras:
Pero ninguno de estos refinamientos conduce a un algoritmo mejor que la inserción directa [es decir, ordenación por inserción ]; y ya sabemos que la inserción recta no es adecuada para N grande . [...] En resumen, el tipo burbuja parece no tener nada que lo recomiende, excepto un nombre pegadizo y el hecho de que conduce a algunos problemas teóricos interesantes.
—DE Knuth [1]
{{cite book}}: |journal=ignorado ( ayuda )