Ordenamiento de burbuja

Clasificación por intercambios simples , clasificación por burbuja ( en inglés bubble sort ) es un algoritmo de clasificación simple . Comprender e implementar este algoritmo es lo más simple, pero solo es efectivo para arreglos pequeños. Complejidad del algoritmo: . $O$ $(n^{2})$

El algoritmo se considera educativo y prácticamente no se usa fuera de la literatura educativa; en cambio, en la práctica se usan algoritmos de clasificación más eficientes. Al mismo tiempo, el método de clasificación de intercambio es la base de algunos de los algoritmos más avanzados, como la clasificación agitadora , la clasificación en montón y la clasificación rápida .

Algoritmo

El algoritmo consiste en pases repetidos a través de la matriz ordenada. Para cada pase, los elementos se comparan secuencialmente en pares y, si el orden en el par es incorrecto, los elementos se permutan. Los pases a través de la matriz se repiten una vez o hasta que en la siguiente pasada resulta que los intercambios ya no son necesarios, lo que significa que la matriz está ordenada. Con cada paso del algoritmo a través del ciclo interno, el siguiente elemento más grande de la matriz se coloca en su lugar al final de la matriz junto al "elemento más grande" anterior, y el elemento más pequeño se mueve una posición al comienzo de la matriz. matriz ("flota" a la posición deseada, como una burbuja en el agua, de ahí el nombre del algoritmo). $N-1$

Implementación

Dificultad: . $O(n^{2})$

Peor de los casos:

El número de comparaciones en el cuerpo del bucle es . $(N-1){\frac N2}$
El número de comparaciones en los encabezados de bucle es . $(N-1){\frac N2}$
El número total de comparaciones es . $(N-1)N$
El número de asignaciones en los encabezados de bucle es . $(N-1){\frac N2}$
El número de intercambios es igual a , que es veces más que en la ordenación por selección . $(N-1){\frac N2}$ ${\ fracción N2}$

En el mejor de los casos (se ingresa una matriz ya ordenada):

El número de comparaciones en el cuerpo del bucle es . $(N-1){\frac N2}$
El número de comparaciones en los encabezados de bucle es . $(N-1){\frac N2}$
El número total de comparaciones es . $(N-1)N$
El número de intercambios es . ${\ estilo de visualización 0}$

La peculiaridad de este algoritmo es la siguiente: después de completar por primera vez el ciclo interno, el elemento máximo de la matriz siempre está en la posición -ésima. En la segunda pasada, el siguiente elemento más grande está en su lugar. Y así. Por lo tanto, en cada pasada subsiguiente, el número de elementos procesados se reduce en 1 y no hay necesidad de "recorrer" toda la matriz de principio a fin cada vez. $norte$ $N-1$

Dado que no es necesario ordenar un subarreglo de un elemento, la ordenación no requiere más que iteraciones del ciclo externo. Por lo tanto, en algunas implementaciones, el bucle externo siempre se ejecuta sin problemas y no realiza un seguimiento de si hubo o no intercambios en cada iteración. $N-1$ $N-1$

La introducción de un indicador (bandera F) de intercambios reales en el bucle interno reduce el número de pases adicionales en casos con matrices de entrada parcialmente clasificadas. Antes de cada paso por el ciclo interno, el indicador se restablece a 0 y, después de que se produzca el intercambio, se establece en 1. Si el indicador es 0 después de salir del ciclo interno, entonces no hubo intercambios, es decir, la matriz está ordenado y puede salir del programa de clasificación antes de lo previsto.

Pseudocódigo para un algoritmo aún más mejorado con verificación de intercambios realmente ocurridos en el bucle interno.

Entrada: matriz que consta de elementos, numerados de a $UN]$ $norte$ ${\ estilo de visualización A [0]}$ ${\ estilo de visualización A [N-1]}$

BUCLE PARA J = 1 A N - 1 PASO 1 PARA J = 1 A N - 1 PASO 1 F = 0 F = 0 BUCLE PARA I = 0 A N - 1 - J PASO 1 PARA I = 0 A N - 1 - J PASO 1 SI A [ I ] > A [ I + 1 ] ENTONCES INTERCAMBIAR A [ I ], A [ I + 1 ]: F = 1 SI A [ I ] > A [ I + 1 ] ENTONCES INTERCAMBIAR A [ I ], A [ I + 1 ]: F = 1 SIGUIENTE I SIGUIENTE I SI F = 0 ENTONCES SALIR DEL BUCLE SI F = 0 ENTONCES SALIR PARA EL SIGUIENTE J SIGUIENTE J

En el caso de una salida anticipada de la clasificación, este algoritmo realiza una pasada redundante sin intercambios.

Peor caso (no mejora):

El número de comparaciones en el cuerpo del bucle es . $(N-1){\frac N2}$
Número de comparaciones en encabezados de bucle . $(N-1){\frac N2}$
El número total de comparaciones es . $(N-1)N$
El número de asignaciones en los encabezados de bucle es . $(N-1){\frac N2}$
El número de intercambios es . $(N-1){\frac N2}$

Mejor caso (mejorado):

El número de comparaciones en el cuerpo del bucle es . $(N-1)$
Número de comparaciones en encabezados de bucle . $(N-1)$
El número total de comparaciones es . $2(N-1)$
El número de intercambios es . ${\ estilo de visualización 0}$

El tiempo de clasificación de 10.000 enteros cortos en el mismo complejo de hardware y software (operación de comparación ≈3,4 µs, intercambio ≈2,3 µs) por clasificación por selección fue de ≈40 segundos, por clasificación de burbuja aún más mejorada ≈30 segundos y por clasificación rápida ≈ 0,027 segundo.

$O(n\cdot n)$ más grande que merge sort , pero en pequeño la diferencia no es muy grande, y el código del programa es muy simple, por lo que es bastante aceptable usar bubble sort para muchas tareas con matrices de baja dimensión en máquinas inactivas y con poca carga. $O(n\cdot\log n)$ $norte$

El algoritmo se puede mejorar ligeramente haciendo lo siguiente:

El bucle interno se puede modificar para que explore alternativamente la matriz desde el principio y luego desde el final. Un algoritmo modificado de esta manera se denomina clasificación aleatoria o clasificación agitadora. Esto no reduce la complejidad . $O(n\cdot n)$

En la ordenación de burbuja, con cada paso a través del ciclo interno, puede agregar la definición del siguiente elemento mínimo y colocarlo al comienzo de la matriz, es decir, combinar los algoritmos de ordenación de burbuja y ordenación de selección , mientras que el número de pases a través el bucle interior se reduce a la mitad, pero el número de comparaciones y un intercambio se añaden después de cada pasada por el bucle interior.

Pseudocódigo del algoritmo combinado de clasificación de burbuja y clasificación de selección ( implementación estable ):

PARA J = 0 A N - 1 PASO 1 F = 0 MIN = J PARA I = J A N - 1 - J PASO 1 SI Y [ I ] > Y [ I + 1 ] ENTONCES INTERCAMBIAR Y [ I ], Y [ I + 1 ]: F = 1 SI Y [ I ] < Y [ MIN ] ENTONCES MIN = I SIGUIENTE I SI F = 0 ENTONCES SALIR PARA SI MIN <> J ENTONCES INTERCAMBIAR Y [ J ], Y [ MIN ] SIGUIENTE J

Un ejemplo de cómo funciona el algoritmo

Tomemos una matriz con los números "5 1 4 2 8" y ordenemos los valores en orden ascendente usando la clasificación de burbujas. Se destacan aquellos elementos que se comparan en esta etapa.

Primer pase:

( 5 1 4 2 8) ( 1 5 4 2 8), Aquí el algoritmo compara los dos primeros elementos y los intercambia. (1 5 4 2 8) (1 4 5 2 8), Intercambios porque

5>4

(1 4 5 2 8) (1 4 2 5 8), Intercambios porque

5>2

(1 4 2 5 8 ) (1 4 2 5 8 ), Ahora, dado que los elementos están en sus lugares ( ), el algoritmo no los intercambia.

8>5

Segundo pase:

( 1 4 2 5 8) ( 1 4 2 5 8) (1 4 2 5 8) (1 2 4 5 8), Intercambios porque

4>2

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

Ahora la matriz está completamente ordenada, pero el algoritmo no lo sabe. Por lo tanto, necesita hacer un pase completo y determinar que no hubo permutaciones de elementos.

Tercer pase:

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

Ahora la matriz está ordenada y el algoritmo puede completarse.

Enlaces

Animación de algoritmos de clasificación
Visualización dinámica 7 Algoritmos de clasificación de código abierto
Levitin A. V. Capítulo 3. Método de fuerza bruta: Bubble sort // Algoritmos. Introducción al desarrollo y análisis - M .: Williams , 2006. - S. 144-146. — 576 pág. — ISBN 978-5-8459-0987-9

diccionarios y enciclopedias	gran chino

Algoritmos de clasificación
Teoría	Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo
Intercambio	burbuja Emocionante enanos Rápido Peine Clasificación par-impar bit a bit
Elección	Elección Piramidal Suave
Inserciones	Inserciones cáscara árbol
fusión	fusión
sin comparaciones	Contando bloquear
híbrido	introsorteo Timsort
Otro	topológico redes bitón
poco práctico	Bogosort Tipo de títere tortita lento