El tipo de coctelera , [1] también conocido como tipo de burbuja bidireccional , [2] tipo de cóctel , tipo de coctelera (que también puede referirse a una variante de tipo de selección ), tipo de ondulación , tipo aleatorio , [3] o tipo de lanzadera , es un extensión del tipo de burbuja . El algoritmo extiende 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.
Clase | Algoritmo de clasificación |
---|---|
Estructura de datos | Formación |
Rendimiento en el peor de los casos | |
Rendimiento en el mejor de los casos | |
Rendimiento medio | |
Complejidad espacial en el peor de los casos |
Como la mayoría de las variantes del tipo de burbujas, el tipo de coctelera se utiliza principalmente como una herramienta educativa. Las bibliotecas de ordenación integradas en lenguajes de programación populares como Python y Java utilizan algoritmos más eficaces , como timsort o merge sort . [4] [5]
Pseudocódigo
La forma más simple recorre toda la lista cada vez:
procedimiento cocktailShakerSort (A : lista de elementos clasificables) es hacer intercambiado: = falso para cada i en 0 a la longitud (A) - 2 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]) // deja que los dos elementos cambien de lugar intercambiado: = verdadero end if end for if no swapped then // podemos salir del bucle externo aquí si no ocurrieron intercambios. romper el final del ciclo do-while si intercambiado: = falso para cada i de longitud (A) - 2 a 0 hacer: si A [i]> A [i + 1] entonces intercambio (A [i], A [i + 1]) intercambiado: = verdadero end if end for while swapped // si no se han intercambiado elementos, entonces la lista se ordena fin procedimiento
El primer pase hacia la derecha desplazará el elemento más grande a su lugar correcto al final, y el siguiente pase 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 que pase i , el primer i y el último i elementos 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 de 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 verificarbeginIdx = 1 ; endIdx = longitud ( A ) - 1 ; while beginIdx <= endIdx newBeginIdx = endIdx ; newEndIdx = beginIdx ; para ii = beginIdx : endIdx si A ( ii ) > A ( ii + 1 ) [ A ( ii + 1 ), A ( ii )] = repartir ( A ( ii ), A ( ii + 1 )); newEndIdx = ii ; final final % 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 )] = repartir ( A ( ii ), A ( ii + 1 )); newBeginIdx = ii ; final final % aumenta `beginIdx` porque los elementos antes de` newBeginIdx` están en el orden correcto beginIdx = newBeginIdx + 1 ; finalfinal
Diferencias con la clasificación de burbujas
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 un tipo de burbuja 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 prueba este punto es la lista (2, 3, 4, 5, 1), que solo necesitaría pasar por una pasada de clasificación de cóctel para clasificarse, pero si se usa una clasificación de burbuja ascendente se necesitarían cuatro pasa. Sin embargo, un pase de clasificación de cóctel debe contarse como dos pases de clasificación de burbujas. Normalmente, la clasificación por cócteles es menos de dos veces más rápida que la clasificación por 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 pasadas más cortas. A medida que el tipo de coctelera va bidireccionalmente, el rango de posibles intercambios, que es el rango que se va a probar, se reducirá por pasada, lo que reducirá ligeramente el tiempo de funcionamiento general.
Complejidad
La complejidad del tipo de coctelera en notación O grande es tanto para el peor de los casos como para el caso medio, pero se acerca a si la lista está mayoritariamente ordenada antes de aplicar el algoritmo de ordenación. Por ejemplo, si cada elemento está en una posición que difiere como máximo k (k ≥ 1) de la posición en la que va a terminar, la complejidad del tipo de coctelera se vuelve
El tipo de coctelera también se analiza brevemente en el libro The Art of Computer Programming , junto con refinamientos similares de tipo 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, la ordenación por inserción ]; y ya sabemos que la inserción recta no es adecuada para N grandes . [...] En resumen, el tipo de burbuja no parece tener nada que lo recomiende, excepto un nombre pegadizo y el hecho de que conduce a algunos problemas teóricos interesantes.
- DE Knuth [1]
Referencias
- ↑ a b c Knuth, Donald E. (1973). "Clasificación por intercambio". Arte de la programación informática . 3. Clasificació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). "clasificación de burbuja bidireccional". En negro, Paul E. (ed.). Diccionario de algoritmos y estructuras de datos . 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, Martin (1986). "Die schrittweise Entwicklung und Beschreibung einer Shuffle-Sort-Array Schaltung". HYPERKARL aus der Algorithmischen Darstellung des BUBBLE-SORT-ALGORITHMUS . Projektarbeit (en alemán). Universidad Técnica de Kaiserslautern.
- ^ "[JDK-6804124] (coll) Reemplace" mergesort modificado "en java.util.Arrays.sort con timsort - Java Bug System" . bugs.openjdk.java.net . Consultado el 11 de enero de 2020 .
- ^ Peters, Tim (20 de julio de 2002). "Clasificación [Python-Dev]" . Consultado el 11 de enero de 2020 .
Fuentes
- Hartenstein, R. (julio de 2010). "Un nuevo modelo mundial de la informática" (PDF) . El gran desafío para reinventar la informática . Belo Horizonte , Brasil: CSBC. Archivado desde el original (PDF) el 7 de agosto de 2013 . Consultado el 14 de enero de 2011 .