Clasificación técnicas de programación: a clasificación "burbulla"

Bubble Sort non só se considera a ser o método máis rápido, ademais, pecha a lista das formas máis lentos para organizar. Con todo, ten as súas vantaxes. Así, o método de clasificación de burbulla - o máis que nin é unha solución natural e lóxica para o problema, se quere organizar os elementos nunha orde específica. Unha persoa común manualmente, por exemplo, que vai usalos - só por intuición.

Onde é que un nome tan raro?

nome do método xurdiu, usando a analoxía de burbullas de aire na auga. É unha metáfora. Así como pequenas burbullas de aire soben para arriba - por que a súa densidade é maior que un fluído (neste caso - a auga), e cada elemento da matriz, o máis pequeno é o valor, o modo máis gradual arriba dos números da lista.

Descrición do algoritmo

Bubble Sort realízase do seguinte xeito:

• Primeira pasada: os elementos dos números de matriz é tomada polos dous pares e tamén comparada. Algúns elementos do equipo de primeira valor de dous homes é maior que o segundo, o programa fai partes de cambio;
• en consecuencia, o maior número de erros a fin da matriz. Mentres todos os outros elementos permanecen como eran, dun xeito caótica, e requiren máis de selección;
• e, polo tanto, requiren un segundo paso: é feita por analoxía co anterior (xa descrito) e ten un número de comparacións - menos un;
• no nero de paso de tres comparacións, un menos que o segundo, ea dous, que a primeira. E así por diante;
• resumir que cada paso ten (todos os valores na matriz, o número particular) de menos (número de paso) comparacións.

Aínda máis curto algoritmo dun programa pode ser escrito como:

• unha serie de números é comprobado, sempre que os dous números son encontrados, a segunda delas é obrigado a ser maior que o primeiro;
• posicionadas de forma incorrecta en relación uns ós outros elementos das permutas de software matriz.

Pseudocódigo baseado no algoritmo descrito

A posta en marcha máis sinxela se realiza do seguinte xeito:

procedemento Sortirovka_Puzirkom;

comezo

ciclo para j de nachalnii_index para konechii_index;

ciclo para i de nachalnii_index para konechii_index-1;

se massiv [i]> massiv [i + 1] (primeiro elemento maior que un segundo), entón:

(Cambio pon valores);

final

Por suposto, esta simplicidade só agrava a situación: canto máis simple o algoritmo, máis ela se manifesta todos os fallos. taxa de investimento de tempo é moi grande ata para unha pequena array (aquí vén na relatividade: A cantidade de tempo para o leigo pode parecer pequena, pero en realidade un programador cada segundo ou mesmo milissegundo conta).

Levou a mellor implementación. Por exemplo, tendo en conta o intercambio de valores en lugares de matriz:

procedemento Sortirovka_Puzirkom;

comezo

sortirovka = true;

ciclo ata sortirovka = true;

sortirovka = false;

ciclo para i de nachalnii_index para konechii_index-1;

se massiv [i]> massiv [i + 1] (primeiro elemento maior que un segundo), entón:

(Cambiar elementos locais);

sortirovka = true; (Identificado que o intercambio foi feita).

End.

limitacións

A desvantaxe principal - a duración do proceso. Canto tempo se realiza algoritmo de ordenación burbulla?

tempo de avance calcúlase a partir do número de números de cadrados na matriz - o resultado final é proporcional.

Se o peor caso a matriz é pasado tantas veces como ten elementos menos un valor. Isto débese a que ao final non é só un elemento, que non teñen nada para comparar, eo último pase a través da matriz se fai acción inútil.

Ademais, o método eficaz de selección un intercambio simple, como se chama, só para matrices de tamaño pequeno. Grandes cantidades de datos coa axuda de proceso non vai funcionar: o resultado será un erro ou fallo do programa.

dignidade

Bubble Sort é moi doado de entender. Os currículos das universidades técnicas no estudo dos elementos de ordenación da súa variedade pasar en primeiro lugar. O método é fácil de implementar tanto a linguaxe Delphi de programación (L (Delphi), e do C / C ++ (C / C plus plus), un incrible simple valores de algoritmo de localización na orde correcta e no Pascal (Pascal). Bubble Sort é ideal para principiantes.

Debido ás desvantaxes do algoritmo non se usa en fins extraescolares.

principio de clasificación Visual

A vista inicial da 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 74 4 44 37 7

Paso 2 1 8 4 22 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 1 4 6 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Paso 7 1 4 7 8 22 37 44 74

exemplo bubble sort en Pascal

exemplo:

kol_mas const = 10;

var massiv: matriz [1..kol_mas] de número enteiro;

a, b, k: enteiro;

comezar

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

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

para un: = 1 a kol_mas-1 fai comezar

para b: = a + 1 a kol_mas comezaren

se massiv [a]> massiv [ b] entón comezar

k: = massiv [a]; massiv [a]: = massiv [ b]; massiv [b]: = k;

acabar;

acabar;

acabar;

writeln ( 'despois tipo');

para un: = 1 a kol_mas facer writeln (massiv [a ]);

fin.

EXEMPLO burbulla selección en linguaxe C (C)

exemplo:

#include

#include

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

{

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

para (;;) {

ff = 0;

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

se (massiv [i] [I- 1]) {

permuta (massiv [i], massiv [I- 1]);

ff ++;

}

}

se (ff == 0) romper;

}

getch (); // atraso de visualización

Return 0;

}.