La clasificación de burbujas no solo no se considera la másEl método rápido, además, cierra la lista de los métodos más lentos de ordenar. Sin embargo, tiene sus ventajas. Por lo tanto, la clasificación por burbujas es la solución más lógica y natural a un problema, si necesita organizar los elementos en un cierto orden. Una persona común, manualmente, por ejemplo, se aprovechará de él, solo por intuición.
¿De dónde viene este nombre inusual?
El nombre del método se inventó usando una analogía conburbujas de aire en el agua. Esta es una metáfora. Así como las pequeñas burbujas de aire se elevan hacia arriba, después de todo, su densidad es mayor que la de cualquier líquido (en este caso, el agua), por lo que cada elemento de la matriz, cuanto menor es su valor, más gradualmente se abre camino hacia el principio. de la lista de números.
Descripción del algoritmo
La clasificación de burbujas se realiza de la siguiente manera:
- primer paso: los elementos de la matriz de números se toman de dos en dos y también se comparan en pares. Si en algunos dos elementos el primer valor resulta ser mayor que el segundo, el programa intercambia sus lugares;
- por lo tanto, el número más grande termina al final de la matriz. Mientras que todos los demás elementos permanecen, como estaban, en un orden caótico y aún requieren clasificación;
- por lo tanto, el segundo paso es necesario: se realiza por analogía con el anterior (ya descrito) y tiene el número de comparaciones - menos uno;
- el pase número tres tiene una comparación menos que el segundo y dos menos que el primero. Etc;
- para resumir, cada pasada tiene (valores totales en la matriz, un número específico) menos (número de pasada) comparaciones.
Aún más breve, el algoritmo del programa futuro se puede escribir de la siguiente manera:
- se comprueba una matriz de números hasta que se encuentran dos números cualesquiera, y el segundo de ellos debe ser mayor que el primero;
- el programa intercambia los elementos de la matriz ubicados incorrectamente entre sí.
Pseudocódigo basado en el algoritmo descrito
La implementación más simple es la siguiente:
Procedimiento Sortirovka_Puzirkom;
El comienzo
ciclo para j desde nachalnii_index antes konechii_index;
ciclo para y desde nachalnii_index antes konechii_index-1;
si un massiv [i]> massiv [i + 1] (el primer elemento es mayor que el segundo), entonces:
(cambiar los valores en lugares);
el fin
Por supuesto, aquí la simplicidad solo exacerbasituación: cuanto más simple es el algoritmo, más todas las deficiencias aparecen en él. El costo del tiempo es demasiado alto incluso para una matriz pequeña (aquí entra en juego la relatividad: para un profano, la cantidad de tiempo puede parecer pequeña, pero en el negocio de un programador, cada segundo o incluso un milisegundo cuenta).
Se requería una mejor implementación. Por ejemplo, teniendo en cuenta el intercambio de valores en la matriz por lugares:
Procedimiento Sortirovka_Puzirkom;
El comienzo
sortirovka = verdadero;
ciclo adiós sortirovka = verdadero;
sortirovka = falso;
ciclo para y desde nachalnii_index antes konechii_index-1;
si un massiv [i]> massiv [i + 1] (el primer elemento es mayor que el segundo), entonces:
(intercambiamos los elementos en lugares);
sortirovka = verdadero; (indicó que se realizó el intercambio).
El fin
Desventajas del método
La principal desventaja es la duración del proceso. ¿Cuánto tiempo tarda el algoritmo de clasificación de burbujas?
El tiempo de ejecución se calcula a partir del cuadrado del número de números en la matriz; el resultado final es proporcional a él.
En el peor de los casos, la matriz se atravesarátantas veces como elementos haya menos un valor. Esto se debe a que al final solo queda un elemento sin nada con qué comparar, y la última pasada a través de la matriz se convierte en una acción inútil.
Además, el método de clasificación por simpleintercambios, como también se le llama, solo para arreglos pequeños. No será posible procesar grandes cantidades de datos con su ayuda: el resultado serán errores o una falla del programa.
Ventajas
La clasificación de burbujas es muy fácil de entender.En los planes de estudio de las universidades técnicas, cuando se estudia el orden de los elementos de la matriz, es el primer paso. El método se implementa fácilmente tanto en el lenguaje de programación Delphi (D (Delphi) como en C / C ++ (C / C plus plus), un algoritmo increíblemente simple para organizar los valores en el orden correcto, y en Pascal. es ideal para principiantes.
Debido a deficiencias, el algoritmo no se utiliza para fines extracurriculares.
Principio de clasificación claro
Vista inicial de la matriz 8 22 4 74 44 37 1 7
Paso 1 8 22 4 74 44 37 1 7
8 22 4 74 44 1 37 7
8 22 4 74 1 44 37 7
8 22 4 1 74 44 37 7
8 22 1 4 74 44 37 7
8 1 22 4 74 44 37 7
1 8 22 4 74 44 37 7
Paso 2 1 8 22 4 74 44 7 37
1 8 22 4 74 7 44 37
1 8 22 4 7 74 44 37
1 8 22 4 7 74 44 37
1 8 4 22 7 74 44 37
1 4 8 22 7 74 44 37
Paso 3 1 4 8 22 7 74 37 44
1 4 8 22 7 37 74 44
1 4 8 22 7 37 74 44
1 4 8 7 22 37 74 44
1 4 7 8 22 37 74 44
Paso 4 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Paso 5 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Paso 6 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Paso 7 1 4 7 8 22 37 44 74
Ejemplo de clasificación de burbujas en Pascal
Ejemplo:
const kol_mas = 10;
var massiv: matriz [1..kol_mas] de entero;
a, b, k: número entero;
empezar
Writeln ("entrada", kol_mas, "elementos de la matriz");
para a: = 1 a kol_mas do readln (massiv [a]);
para un: = 1 a kol_mas-1 comience
para b: = a + 1 to kol_mas do begin
si massiv [a]> massiv [b] entonces comience
k: = massiv [a]; massiv [a]: = massiv [b]; massiv [b]: = k;
fin;
fin;
fin;
Writeln ("después de ordenar");
para a: = 1 a kol_mas do writeln (massiv [a]);
fin.
Un ejemplo de clasificación de burbujas en C (C)
Ejemplo:
#incluir
#incluir
int main (int argc, char * argv [])
{
int massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff;
por (;;) {
ff = 0;
para (i = 7; i> 0; i -) {
si (massiv [i] <massiv [i-1]) {
intercambio (massiv [i], massiv [i-1]);
ff ++;
}
}
si (ff == 0) romper;
}
getch (); // retraso de la pantalla
return 0;
}.
