Métodos de clasificación en programación: clasificación por "burbuja"

Clasificar por burbuja no solo no se considera el máspor un método rápido, además, cierra la lista de las formas más lentas de ordenar. Sin embargo, también tiene sus ventajas. Por lo tanto, ordenar por el método de burbujas es la solución más lógica y natural para el problema, si desea organizar los elementos en un cierto orden. Una persona ordinaria, por ejemplo, lo usará a mano, simplemente por intuición.

¿De dónde vino 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. Del mismo modo que pequeñas burbujas de aire suben a la cima, debido a que su densidad es mayor que cualquier líquido (en este caso, agua), y cada elemento de la matriz, cuanto menor es su valor, más gradualmente se dirige al principio de la lista de números.

Descripción del algoritmo

La clasificación por burbuja se realiza de la siguiente manera:

• el primer pase: los elementos del conjunto de números se toman en dos y también se comparan por pares. Si en dos de los elementos el primer valor es mayor que el segundo, el programa realiza su intercambio de lugares;
• por lo tanto, el número más grande se encuentra al final de la matriz. Mientras que todos los otros elementos permanecen, como estaban, en un orden caótico y requieren clasificación adicional;
• por lo tanto, se necesita una segunda pasada: se produce por analogía con la anterior (ya descrita) y tiene varias comparaciones, menos una;
• en el pase, las comparaciones número tres son una menos que la segunda, y dos, que la primera. Y así sucesivamente;
• Vamos a resumir que cada pase tiene (en la matriz, un número específico) menos (número de pasadas) comparaciones.

Algún algoritmo más corto del programa futuro se puede escribir de la siguiente manera:

• la matriz de números se verifica hasta que se encuentren dos números, el segundo de los cuales debe ser mayor que el primero;
• ubicado incorrectamente en relación con los otros elementos de la matriz, el programa cambia.

Pseudocódigo basado en el algoritmo descrito

La implementación más simple es la siguiente:

Procedimiento Sortirovka_Puzirkom;

El comienzo

ciclo para j de la nachalnii_index hasta konechii_index;

ciclo para yo de la nachalnii_index hasta konechii_index-1;

si massiv [i]> massiv [i + 1] (el primer elemento es mayor que el segundo), entonces:

(cambie los valores en lugares);

El fin

Por supuesto, aquí la simplicidad solo agravaSituación: cuanto más simple es el algoritmo, más se manifiesta todos los defectos. tasa de inversión de tiempo es demasiado grande incluso para una pequeña gama (aquí viene en la relatividad: La cantidad de tiempo para el profano puede parecer pequeña, pero, de hecho, un programador cada segundo o incluso milisegundo cuenta).

Tomó una mejor implementación. Por ejemplo, teniendo en cuenta el intercambio de valores en la matriz en algunos lugares:

Procedimiento Sortirovka_Puzirkom;

El comienzo

sortirovka = verdadero;

ciclo hasta sortirovka = verdadero;

sortirovka = falso

ciclo para yo de la nachalnii_index hasta konechii_index-1;

si massiv [i]> massiv [i + 1] (el primer elemento es mayor que el segundo), entonces:

(cambiamos 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 funciona el algoritmo de clasificación de burbujas?

El tiempo de ejecución se calcula a partir del cuadrado de la cantidad de números en la matriz; el resultado final es proporcional a la misma.

En el peor de los casos, la matriz se aprobarátantas veces como elementos haya, menos un valor. Esto se debe a que al final solo hay un elemento que no tiene nada con lo que comparar, y el último pase a través de la matriz se convierte en una acción inútil.

Además, el método de clasificación es simpleintercambios, como también se llama, solo para matrices de pequeño tamaño. No se pueden procesar grandes cantidades de datos al usarlo: el resultado será un error o una falla del programa.

Ventajas

Clasificar una burbuja es muy simple de entender. En los planes de estudios de las universidades técnicas, al estudiar el orden de los elementos de una matriz, pasa primero. El método es fácil de implementar tanto el lenguaje Delphi programación (L (Delphi), y la C / C ++ (C / C plus plus), un increíblemente simples valores de algoritmo de localización en el orden correcto y en el Pascal (Pascal). Ordenamiento de burbuja es ideal para principiantes.

Debido a deficiencias, el algoritmo no se utiliza para fines extracurriculares.

Un claro principio de clasificación

La vista inicial de la matriz es 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 una burbuja en Pascal

Ejemplo:

const kol_mas = 10;

var massiv: array [1..kol_mas] de entero;

a, b, k: entero;

comenzar

writeln ("entrada", kol_mas, "elementos de matriz");

para a: = 1 a kol_mas do readln (massiv [a]);

para a: = 1 a kol_mas-1 comienzan

para b: = a + 1 a kol_mas comienzan

si massiv [a]> massiv [b] entonces comienza

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

Ejemplo de clasificación por una burbuja en C (C)

Ejemplo:

#include

#include

int main (int argc, char * argv [])

{

int massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff;

para (;;) {

ff = 0;

para (i = 7; i> 0; i -) {

if (massiv [i] <massiv [i-1]) {

swap (massiv [i], massiv [i-1]);

ff ++;

}

}

if (ff == 0) romper;

}

getch (); // retraso de la pantalla

return 0;

}.