Es un tipo de clasificación, que se utiliza mejor cuando los datos son pequeños. es decir, la lista de elementos a ordenar es baja.
Es el algoritmo de clasificación más simple que funciona intercambiando repetidamente los elementos adyacentes si están en orden incorrecto.
Ejemplo:
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), Intercambiar 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.
- ¿Dónde encuentro los mejores recursos para aprender algoritmos y estructuras de datos?
- Cómo capturar información de color de un anime
- ¿Cuáles son algunas de las mejores plataformas en línea para practicar la codificación relacionada con algoritmos?
- ¿Cómo funciona el algoritmo de creación de coincidencias dota 2?
- ¿Cuál es el algoritmo utilizado por el IRCTC para reservar en línea?
Segundo pase:
( 1 4 2 5 8) -> ( 1 4 2 5 8)
(1 4 2 5 8) -> (1 2 4 5 8), Intercambiar 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 nuestro 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 )
Aquí está el algo para ello:
Suponemos que list es una matriz de n elementos. Suponemos además que la función de intercambio intercambia los valores de elementos de matriz dados.
comenzar BubbleSort (lista)
para todos los elementos de la lista
si lista [i]> lista [i + 1]
swap (lista [i], lista [i + 1])
terminara si
fin de
lista de retorno
Fin BubbleSort
La peor y media complejidad del tiempo del caso: O (n * n). El peor de los casos ocurre cuando la matriz está ordenada inversamente.
Mejor complejidad del tiempo del caso: O (n). El mejor caso ocurre cuando la matriz ya está ordenada.
Espacio auxiliar: O (1)
Casos límite: la ordenación de burbujas toma un tiempo mínimo (orden de n) cuando los elementos ya están ordenados.
Clasificación en el lugar: sí
Estable: sí
Debido a su simplicidad, la clasificación de burbujas se usa a menudo para introducir el concepto de un algoritmo de clasificación.
En gráficos de computadora 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 una complejidad lineal (2n). 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 las intersecciones de dos líneas
Y para que entiendan mejor, aquí está el programa para eso en C ++
// Programa C para la implementación de Bubble sort
#include
intercambio nulo (int * xp, int * yp)
{
int temp = * xp;
* xp = * yp;
* yp = temp;
}
// Una función para implementar el ordenamiento de burbujas
void bubbleSort (int arr [], int n)
{
int i, j;
para (i = 0; i <n-1; i ++)
// Los últimos elementos i ya están en su lugar
para (j = 0; j <ni-1; j ++)
if (arr [j]> arr [j + 1])
swap (& arr [j], & arr [j + 1]);
}
/ * Función para imprimir una matriz * /
vacío printArray (int arr [], int size)
{
para (int i = 0; i <tamaño; i ++)
printf (“% d”, arr [i]);
printf (“\ n”);
}
// Programa de controlador para probar las funciones anteriores
int main ()
{
int arr [] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof (arr) / sizeof (arr [0]);
bubbleSort (arr, n);
printf (“Matriz ordenada: \ n”);
printArray (arr, n);
devuelve 0;
}
