Hispanopedia WikiEl ordenamiento por agitación de cócteles , [1] también conocido como ordenamiento por burbuja bidireccional , [ 2] ordenamiento por cócteles , ordenamiento por agitación (que también puede referirse a una variante del ordenamiento por selección ), ordenamiento por ondulación , ordenamiento aleatorio [3] o ordenamiento lanzadera , es una extensión del ordenamiento por burbuja . El algoritmo extiende el ordenamiento por burbuja al operar en dos direcciones. Si bien mejora el ordenamiento por burbuja al mover los elementos más rápidamente al principio de la lista , solo proporciona mejoras marginales en el rendimiento.
Al igual que la mayoría de las variantes de ordenamiento de burbuja, el ordenamiento por coctelera se utiliza principalmente como herramienta educativa. Las bibliotecas de ordenamiento integradas en lenguajes de programación populares como Python y Java utilizan algoritmos de mayor rendimiento, como quicksort , merge sort o timsort . [4] [5]
Pseudocódigo
La forma más simple recorre toda la lista cada vez:
El procedimiento cocktailShakerSort(A : lista de elementos ordenables) es
hacer
intercambiado := falso
para cada i en 0 hasta length(A) − 1 hacer:
si A[i] > A[i + 1] entonces // probar si los dos elementos están en el orden incorrecto
swap(A[i], A[i + 1]) // dejar que los dos elementos cambien de lugar
intercambiado := verdadero
fin si
fin para
si no se intercambia entonces
// podemos salir del bucle externo aquí si no se produjeron intercambios.
romper bucle do-while
fin si
intercambiado := falso
para cada i de longitud (A) − 1 a 0 hacer:
si A[i] > A[i + 1] entonces
intercambiar(A[i], A[i + 1])
intercambiado := verdadero
fin si
fin para
mientras intercambiado // si no se han intercambiado elementos, entonces la lista se ordena
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. El segundo paso completo desplazará el segundo elemento más grande y el segundo más pequeño a sus lugares correctos, y así sucesivamente. Después de i pases, el primer i y el último i elementos de la lista están en sus posiciones correctas y no necesitan ser revisados. Al acortar la parte de la lista que se ordena cada vez, el número de operaciones se puede reducir a la mitad (ver ordenamiento de burbuja ).
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 a comprobar beginIdx = 1 ; endIdx = length ( A ) -1 ; mientras beginIdx <= endIdx newBeginIdx = endIdx ; newEndIdx = beginIdx ; para ii = beginIdx : endIdx si A ( ii ) > A ( ii + 1 ) [ A ( ii + 1 ), A ( ii )] = deal ( A ( ii ), A ( ii + 1 ) ); newEndIdx = 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 : beginIdx si A ( ii ) > A ( ii + 1 ) [ A ( ii + 1 ), A ( ii )] = deal ( A ( ii ), A ( ii + 1 )); newBeginIdx = ii ; end end % aumenta `beginIdx` porque los elementos antes de `newBeginIdx` están en el orden correcto beginIdx = newBeginIdx + 1 ; end end
Diferencias con la clasificación de burbuja
El ordenamiento por coctelera es una ligera variación del ordenamiento por burbuja . [1] Se diferencia en que, en lugar de recorrer repetidamente 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 un ordenamiento por burbuja estándar. La razón de esto es que el ordenamiento por burbuja solo recorre la lista en una dirección y, por lo tanto, solo puede mover los elementos un paso hacia atrás 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 ordenación de cóctel para quedar ordenada, pero si se utiliza una ordenación de burbuja ascendente necesitaría cuatro pasadas. Sin embargo, una pasada de ordenación de cóctel debe contarse como dos pasadas de ordenación de burbuja. Normalmente, la ordenación de cóctel es menos de dos veces más rápida que la ordenación de burbuja.
Otra optimización puede ser que el algoritmo recuerde dónde se realizó el último intercambio real. En la siguiente iteración, no habrá intercambios más allá de este límite y el algoritmo tendrá pases más cortos. Como la ordenación con coctelera se realiza de forma bidireccional, el rango de posibles intercambios, que es el rango que se va a probar, se reducirá por pase, lo que reducirá ligeramente el tiempo total de ejecución.
Complejidad
La complejidad de la ordenación por coctelera en notación O mayúscula es tanto para el peor caso como para el caso promedio, pero se acerca más a si la lista está mayormente ordenada antes de aplicar el algoritmo de ordenació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 terminará, la complejidad de la ordenación por coctelera se convierte en
El ordenamiento por coctelera también se analiza brevemente en el libro El arte de la programación informática , junto con mejoras similares del ordenamiento por burbuja. En conclusión, Knuth afirma lo siguiente sobre el ordenamiento por burbuja y sus mejoras:
Pero ninguno de estos refinamientos conduce a un algoritmo mejor que la inserción directa [es decir, la ordenación por inserción ]; y ya sabemos que la inserción directa no es adecuada para N grandes . [...] En resumen, la ordenación de burbuja no parece tener nada que la recomiende, excepto un nombre pegadizo y el hecho de que conduce a algunos problemas teóricos interesantes.
— DE Knuth [1]
Variaciones
- Dual Cocktail Shaker Sort es una variante de Cocktail Shaker Sort que realiza un pase hacia adelante y hacia atrás por iteración simultáneamente, lo que mejora el rendimiento en comparación con el original.
Referencias
- ^ abc Knuth, Donald E. (1973). "Ordenación por intercambio". El arte de la programación informática . Vol. 3. Ordenación y búsqueda (1.ª ed.). Addison-Wesley . págs. 110-111. ISBN 0-201-03803-X.
- ^ Black, Paul E.; Bockholt, Bob (24 de agosto de 2009). «bidirectional bubble sort». En Black, Paul E. (ed.). Dictionary of Algorithms and Data Structures. Instituto Nacional de Estándares y Tecnología . Archivado desde el original el 16 de marzo de 2013. Consultado el 5 de febrero de 2010 .
- ^ Duhl, Martín (1986). "Die schrittweise Entwicklung und Beschreibung einer Shuffle-Sort-Array Schaltung". HYPERKARL aus der Algorithmischen Darstellung des BUBBLE-SORT-ALGORITHMUS (en alemán). Universidad Técnica de Kaiserslautern.
{{cite book}}:|journal=ignorado ( ayuda ) - ^ "[JDK-6804124] (coll) Reemplazar "modified mergesort" en java.util.Arrays.sort con timsort - Sistema de errores de Java". bugs.openjdk.java.net . Consultado el 11 de enero de 2020 .
- ^ Peters, Tim (20 de julio de 2002). «[Python-Dev] Ordenación» . Consultado el 11 de enero de 2020 .
Fuentes
- Hartenstein, R. (julio de 2010). "Un nuevo modelo mundial de computación" (PDF) . El gran desafío de reinventar la computación . Belo Horizonte , Brasil: CSBC. Archivado desde el original (PDF) el 2013-08-07 . Consultado el 2011-01-14 .
Enlaces externos
- Demostración interactiva de clasificación de cócteles
- Código fuente de Java y una demostración animada de ordenamiento por cóctel (llamado ordenamiento por burbuja bidireccional) y varios otros algoritmos
- "Implementación en .NET de ordenamiento por cócteles y otros algoritmos". Archivado desde el original el 12 de febrero de 2012.
