LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

La clasificación de burbujas , a veces denominada clasificación de hundimiento , es un algoritmo de clasificación simple que recorre repetidamente la lista, compara elementos adyacentes y los intercambia si están en el orden incorrecto. El paso por la lista se repite hasta que se ordena la lista. El algoritmo, que es un tipo de comparación , se nombra por la forma en que los elementos más pequeños o más grandes "burbuja" en la parte superior de la lista. Aunque el algoritmo es simple, es demasiado lento y poco práctico para la mayoría de los problemas, incluso en comparación con el tipo de inserción . ^{[2] La} clasificación de burbujas puede ser práctica si la entrada está en su mayoría ordenada con algunos elementos fuera de orden casi en posición.

Ordenamiento de burbuja

Visualización estática del tipo burbuja [1]
Clase	Algoritmo de clasificación
Estructura de datos	Formación
El peor de los casos	$${\ displaystyle O (n ^ {2})} comparaciones, $${\ displaystyle O (n ^ {2})} permutas
El mejor rendimiento	$${\ displaystyle O (n)} comparaciones, $${\ displaystyle O (1)} permutas
Rendimiento medio	$${\ displaystyle O (n ^ {2})} comparaciones, $${\ displaystyle O (n ^ {2})} permutas
La peor complejidad del espacio	$${\ displaystyle O (1)} auxiliar

Análisis [ editar ]

Un ejemplo de clasificación de burbujas. Comenzando desde el principio de la lista, compare cada par adyacente, cambie su posición si no están en el orden correcto (el último es más pequeño que el anterior). Después de cada iteración , se necesita comparar un elemento menos (el último) hasta que no queden más elementos para comparar.

Rendimiento [ editar ]

La clasificación de burbujas tiene una complejidad promedio y de peor caso de О ( n ² ), donde n es el número de elementos que se ordenan. La mayoría de los algoritmos de clasificación prácticos tienen una complejidad promedio o peor en el peor de los casos, a menudo O ( n  log  n ). Incluso otros algoritmos de ordenamiento О ( n ² ), como el ordenamiento por inserción , generalmente se ejecutan más rápido que el ordenamiento por burbujas, y no son más complejos. Por lo tanto, la clasificación de burbujas no es un algoritmo práctico de clasificación.

La única ventaja significativa que tiene la ordenación de burbujas sobre la mayoría de los otros algoritmos, incluso la ordenación rápida , pero no la ordenación por inserción , es que la capacidad de detectar que la lista está ordenada de manera eficiente está integrada en el algoritmo. Cuando la lista ya está ordenada (el mejor de los casos), la complejidad del ordenamiento de burbujas es solo O ( n ). Por el contrario, la mayoría de los otros algoritmos, incluso aquellos con una mejor complejidad de caso promedio , realizan todo su proceso de clasificación en el conjunto y, por lo tanto, son más complejos. Sin embargo, la clasificación de inserción no solo comparte esta ventaja, sino que también funciona mejor en una lista que está clasificada sustancialmente (que tiene un pequeño número de inversiones ).

El tipo de burbuja debe evitarse en el caso de grandes colecciones. No será eficiente en el caso de una colección ordenada inversamente.

Conejos y tortugas [ editar ]

La distancia y la dirección que deben mover los elementos durante la clasificación determina el rendimiento de la clasificación de burbujas porque los elementos se mueven en diferentes direcciones a diferentes velocidades. Un elemento que debe moverse hacia el final de la lista puede moverse rápidamente porque puede participar en intercambios sucesivos. Por ejemplo, el elemento más grande en la lista ganará cada intercambio, por lo que se mueve a su posición ordenada en la primera pasada, incluso si comienza cerca del principio. Por otro lado, un elemento que debe moverse hacia el comienzo de la lista no puede moverse más rápido que un paso por pase, por lo que los elementos se mueven hacia el comienzo muy lentamente. Si el elemento más pequeño está al final de la lista, tomará n −1pasa para moverlo al principio. Esto ha llevado a que este tipo de elementos se denominen conejos y tortugas, respectivamente, después de los personajes de la fábula de Esopo de La tortuga y la liebre .

Se han realizado varios esfuerzos para eliminar las tortugas para mejorar la velocidad de clasificación de burbujas. La clasificación de cóctel es una clasificación de burbujas bidireccional que va de principio a fin y luego se invierte, de principio a fin. Puede mover a las tortugas bastante bien, pero conserva la complejidad de O (n ² ) en el peor de los casos. La clasificación de peine compara elementos separados por grandes espacios, y puede mover tortugas extremadamente rápido antes de pasar a espacios cada vez más pequeños para suavizar la lista. Su velocidad promedio es comparable a algoritmos más rápidos como quicksort .

Ejemplo paso a paso [ editar ]

Tome una matriz de números "5 1 4 2 8", y ordene la matriz del número más bajo al número más grande usando la clasificación de burbujas. En cada paso, se comparan elementos escritos en negrita . Se requerirán tres pases;

Primer pase

( 5 1 4 2 8) → ( 1 5 4 2 8), Aquí, el algoritmo compara los dos primeros elementos y cambia desde 5> 1.

(1 5 4 2 8) → (1 4 5 2 8), Intercambiar desde 5> 4

(1 4 5 2 8) → (1 4 2 5 8), Cambiar desde 5> 2

(1 4 2 5 8 ) → (1 4 2 5 8 ), ahora, dado que estos elementos ya están en orden (8> 5), el algoritmo no los intercambia.

Segundo pase

( 1 4 2 5 8) → ( 1 4 2 5 8)

(1 4 2 5 8) → (1 2 4 5 8), Cambiar desde 4> 2

(1 2 4 5 8) → (1 2 4 5 8)

(1 2 4 5 8 ) → (1 2 4 5 8 )

Ahora, la matriz ya está ordenada, pero el algoritmo no sabe si está completa. El algoritmo necesita un pase completo sin ningún intercambio para saber que está ordenado.

Tercer pase

( 1 2 4 5 8) → ( 1 2 4 5 8)

(1 2 4 5 8) → (1 2 4 5 8)

(1 2 4 5 8) → (1 2 4 5 8)

(1 2 4 5 8 ) → (1 2 4 5 8 )

Implementación [ editar ]

Implementación de pseudocódigo [ editar ]

En el pseudocódigo, el algoritmo se puede expresar como (matriz basada en 0):

procedimiento  bubbleSort ( A  :  lista  de  elementos ordenables  ) n = longitud ( A ) repetir intercambiado = falso para i = 1 a n - 1 inclusive do / * si este par está fuera de servicio * / si A [ i - 1 ] > A [ i ] luego / * intercambiar 
      
    
          
               
                    
                
                  ellos  y  recordar  algo  cambiado  * / 
                intercambio (  A [ i - 1 ] ,  A [ i ]  ) 
                intercambiado  =  verdadero 
            final  si 
        final  de 
    hasta  no  intercambiado 
extremo  procedimiento

Optimizando el ordenamiento de burbujas [ editar ]

El algoritmo de ordenamiento de burbuja se puede optimizar fácilmente mediante la observación de que el n pase -ésimo encuentra el n -ésimo elemento más grande y lo pone en su lugar definitivo. Por lo tanto, el bucle interno puede evitar mirar a la última n - 1 elementos cuando se ejecuta para el n tiempo -ésimo:

procedimiento  BubbleSort (  A  :  lista  de  que se pueden ordenar  artículos  ) 
    n  =  longitud ( A ) 
    repetir 
        intercambió  =  falso 
        para  i  =  1  a  n - 1  inclusive  hacer 
            si  A [ i - 1 ]  >  A [ i ]  entonces 
                cambiaré ( A [ i - 1 ] ,  A [ i ])
                intercambiado  =  final verdadero 
            si finaliza para n = n - 1 hasta el procedimiento final no intercambiado 
         
            
      
 

En términos más generales, puede suceder que se coloque más de un elemento en su posición final en una sola pasada. En particular, después de cada pasada, se ordenan todos los elementos después del último intercambio y no es necesario volver a verificarlos. Esto permite omitir muchos elementos, lo que da como resultado una mejora del 50% en el peor de los casos en el recuento de comparación (aunque no mejora en los recuentos de intercambio), y agrega muy poca complejidad porque el nuevo código subsume la variable "intercambiada":

Para lograr esto en pseudocódigo, se puede escribir lo siguiente:

procedimiento  BubbleSort (  A  :  lista  de  que se pueden ordenar  artículos  ) 
    n  =  longitud ( A ) 
    repetir 
        newn  =  0 
        para  i  =  1  a  n - 1  inclusive  hacer 
            si  A [ i - 1 ]  >  A [ i ]  entonces 
                cambiaré ( A [ i - 1 ] ,  A [ i ])
                newn  =  i 
            end  if 
        end  para 
        n  =  newn 
    hasta  n  <=  1 
final  procedimiento

Las modificaciones alternativas, como la clasificación de la coctelera, intentan mejorar el rendimiento de la clasificación de burbujas mientras mantienen la misma idea de comparar e intercambiar repetidamente elementos adyacentes.

Usar [ editar ]

Una ordenación de burbujas, un algoritmo de ordenación que recorre continuamente una lista, intercambiando elementos hasta que aparecen en el orden correcto. La lista se trazó en un sistema de coordenadas cartesianas, con cada punto ( x , y ) que indica que el valor y se almacena en el índice x . Luego, la lista se ordenaría por burbuja según el valor de cada píxel. Tenga en cuenta que el extremo más grande se ordena primero, y los elementos más pequeños tardan más en moverse a sus posiciones correctas.

Aunque la clasificación de burbujas es uno de los algoritmos de clasificación más simples para comprender e implementar, su complejidad O ( n ² ) significa que su eficiencia disminuye drásticamente en las listas de más de un pequeño número de elementos. Incluso entre los algoritmos de clasificación de O ( n ² ) simples , los algoritmos como la clasificación de inserción suelen ser considerablemente más eficientes.

Debido a su simplicidad, la clasificación de burbujas se usa a menudo para presentar el concepto de un algoritmo, o un algoritmo de clasificación, a los estudiantes introductorios de ciencias de la computación . Sin embargo, algunos investigadores como Owen Astrachan han hecho todo lo posible para menospreciar el tipo de burbuja y su continua popularidad en la educación en ciencias de la computación, y recomiendan que ya no se enseñe. ^[3]

El Archivo Jargon , que llama a bogosort "el algoritmo arquetípico [sic] perversamente horrible", también llama a la clasificación de burbujas "el algoritmo genérico malo". ^[4] Donald Knuth , en The Art of Computer Programming , concluyó que "el tipo de burbuja parece no tener nada que lo recomiende, excepto un nombre pegadizo y el hecho de que conduce a algunos problemas teóricos interesantes", algunos de los cuales luego analiza . ^[2]

La ordenación de burbujas es asintóticamente equivalente en tiempo de ejecución a la ordenación por inserción en el peor de los casos, pero los dos algoritmos difieren mucho en la cantidad de intercambios necesarios. Los resultados experimentales como los de Astrachan también han demostrado que la ordenación por inserción funciona considerablemente mejor incluso en listas aleatorias. Por estas razones, muchos libros de texto de algoritmos modernos evitan usar el algoritmo de clasificación de burbujas a favor de la clasificación por inserción.

El tipo de burbuja también interactúa mal con el hardware moderno de la CPU. Produce al menos el doble de escrituras que el tipo de inserción, el doble de errores de caché y asintóticamente más predicciones erróneas de rama . ^{[ cita requerida ] Los} experimentos de Astrachan que ordenan las cadenas en Java muestran que la clasificación de burbujas es aproximadamente un quinto más rápida que una clasificación de inserción y un 70% tan rápida como una clasificación de selección . ^[3]

En los gráficos de computadora, el ordenamiento de burbujas es popular por su capacidad de detectar un error muy pequeño (como el intercambio de solo dos elementos) en arreglos casi ordenados y arreglarlo con solo complejidad lineal (2 n ). Por ejemplo, se usa en un algoritmo de relleno de polígonos, donde las líneas de delimitación se ordenan por su coordenada x en una línea de exploración específica (una línea paralela al eje x ) y al incrementar y su orden cambia (se intercambian dos elementos) solo en intersecciones de dos líneas. La ordenación de burbujas es un algoritmo de ordenación estable, como la ordenación por inserción.

Variaciones [ editar ]

• La clasificación impar-par es una versión paralela de la clasificación de burbujas, para los sistemas de paso de mensajes.
• Los pases pueden ser de derecha a izquierda, en lugar de izquierda a derecha. Esto es más eficiente para listas con elementos sin clasificar agregados al final.
• El tipo de coctelera alterna los pases hacia la izquierda y hacia la derecha.

Debate sobre el nombre [ editar ]

El tipo de burbuja se ha denominado ocasionalmente como un "tipo de hundimiento". ^[5]

Por ejemplo, en The Art of Computer Programming , Volume 3: Sorting and Search de Donald Knuth , afirma en la sección 5.2.1 'Ordenar por inserción', que [el valor] "se establece en su nivel adecuado" y que este método de clasificación tiene a veces se le llama la técnica de tamizado o hundimiento . ^{[ aclaración necesaria ]}

Este debate se perpetúa por la facilidad con la que se puede considerar este algoritmo desde dos perspectivas diferentes pero igualmente válidas:

1. Los valores más grandes pueden considerarse más pesados y, por lo tanto, se ve que se hunden progresivamente al final de la lista
2. Los menores valores podrían ser considerados como más ligero y por lo tanto se ven progresivamente a borbotones a la parte superior de la lista.

En la cultura popular [ editar ]

El CEO de Google, Eric Schmidt, le preguntó al presidente Barack Obama una vez durante una entrevista sobre la mejor manera de clasificar un millón de enteros , y Obama, haciendo una pausa por un momento, respondió: "Creo que el tipo de burbuja sería el camino equivocado". ^[

De Wikipedia, la enciclopedia libre

^{Saltar a navegaciónSaltar a búsqueda}

Tipo de coctelera

Clase	Algoritmo de clasificación
Estructura de datos	Formación
El peor de los casos	$${\ displaystyle O (n ^ {2})}
El mejor rendimiento	$${\ displaystyle O (n)}
Rendimiento medio	$${\ displaystyle O (n ^ {2})}
La peor complejidad del espacio	$${\ displaystyle O (1)}

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 de barajado , ^[3] o tipo de lanzadera , es un variación de ordenamiento de burbuja que es a la vez estable algoritmo de ordenación y una especie de comparación . El algoritmo difiere de un tipo de burbuja.en eso se ordena en ambas direcciones en cada paso a través de la lista. Este algoritmo de clasificación es marginalmente más difícil de implementar que una clasificación de burbujas, y resuelve el problema de las tortugas en forma de burbujas. Proporciona solo mejoras de rendimiento marginales y no mejora el rendimiento asintótico; como el tipo burbuja, no es de interés práctico ( se prefiere el tipo de inserción para los tipos simples), aunque encuentra algún uso en la educación.

Pseudocódigo [ editar ]

La forma más simple pasa por la lista completa cada vez:

procedimiento cocktailShakerSort (A : lista de elementos clasificables) definido como: 
  do
    intercambiado: = falso
    para cada i en 0 a longitud (A) - 2 do: 
      si A [i]> A [i + 1] entonces  // comprueba si los dos elementos están en el 
        intercambio de orden incorrecto (A [i], A [i + 1]) // deja que los dos elementos cambien de lugar
        intercambiado: = verdadero
      end if 
    end for 
    si no se intercambia entonces 
      // podemos salir del bucle externo aquí si no se produjeron intercambios. 
      romper el ciclo do-while 
    final si
    intercambiado: = falso
    para cada i de longitud (A) - 2 a 0 do: 
      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 está ordenada 
fin procedimiento

El primer pase a la derecha desplazará el elemento más grande a su lugar correcto al final, y el siguiente pase a la izquierda desplazará el elemento más pequeño a su lugar correcto al principio. El segundo pase 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 que pase, la primera i y las últimas i elementos de la lista se encuentran 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 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` marca el primer y el último índice para comprobar 
beginIdx  =  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 )]  =  acuerdo ( 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 
        if  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 anteriores a` newBeginIdx` están en el orden correcto
    beginIdx  =  newBeginIdx  +  1 ; 
fin 
fin

Diferencias con el tipo de burbuja [ editar ]

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 a través de 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 un paso de clasificación de cóctel para clasificarse, pero si se usa una clasificación de burbuja ascendente , tomaría cuatro pases Sin embargo, un pase de clasificación de cóctel debe contarse como dos pases de clasificación de burbujas. Por lo general, 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 se realiza bidireccionalmente, el rango de intercambios posibles, que es el rango que se probará, se reducirá por pasada, lo que reducirá ligeramente el tiempo de ejecución general.

Complejidad [ editar ]

La complejidad del tipo de coctelera en notación O grande es$${\ displaystyle O (n ^ {2})} tanto para el peor caso como para el caso promedio, pero se acerca $${\ displaystyle O (n)}si la lista se ordena principalmente 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 va a terminar, la complejidad del tipo de coctelera se convierte en$${\ displaystyle O (kn).}

El tipo de coctelera también se discute brevemente en el libro The Art of Computer Programming , junto con refinamientos similares del tipo de burbuja. En conclusión, Knuth afirma sobre el tipo de burbuja y sus mejoras:

Pero ninguno de estos refinamientos conduce a un algoritmo mejor que la inserción directa [es decir, el tipo de inserción ]; y ya sabemos que la inserción recta no es adecuada para N grande  . [...] En resumen, el tipo de burbuja parece no tener nada que lo recomiende, excepto un nombre pegadizo y el hecho de que conduce a algunos problemas teóricos interesantes.