classificação técnicas de programação: a classificação "bolha"

bubble sort não só é considerado para ser o método mais rápido, além disso, ele fecha a lista das maneiras mais lentos para organizar. No entanto, ele tem suas vantagens. Assim, o método de classificação de bolha – o mais que nem é uma solução natural e lógica para o problema, se você quiser organizar os itens em uma ordem específica. Uma pessoa comum manualmente, por exemplo, ele vai usá-los – apenas por intuição.

Onde é que um nome tão incomum?

nome do método surgiu, usando a analogia de bolhas de ar na água. É uma metáfora. Assim como pequenas bolhas de ar sobem para cima – porque a sua densidade é maior do que um fluido (neste caso – a água), e cada elemento da matriz, o mais pequeno é o valor, o modo mais gradual ao topo dos números da lista.

Descrição do algoritmo

bubble sort é realizada da seguinte forma:

• primeira passagem: os elementos dos números de matriz é tomada pelos dois pares e também comparada. Se alguns elementos da equipa de primeiro valor de dois homens é maior do que o segundo, o programa torna-os lugares de câmbio;
• consequentemente, o maior número de erros a fim da matriz. Enquanto todos os outros elementos permanecem como eles eram, de uma maneira caótica, e requerem mais de triagem;
• e, por conseguinte, requerem um segundo passo: é feita por analogia com o anterior (já descrito) e tem um número de comparações – menos um;
• no nero de passagem de três comparações, um a menos do que o segundo, e a dois, do que o primeiro. E assim por diante;
• resumir que cada passagem tem (todos os valores na matriz, o número particular) de menos (número de passagem) comparações.

Ainda mais curto algoritmo de um programa pode ser escrito como:

• uma série de números é verificado, desde que quaisquer dois números são encontrados, o segundo deles é obrigado a ser maior do que o primeiro;
• posicionadas de forma incorrecta em relação uns aos outros elementos das permutas de software matriz.

Pseudocódigo baseado no algoritmo descrito

A implementação mais simples é realizada da seguinte forma:

procedimento Sortirovka_Puzirkom;

começo

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 do que um segundo), então:

(Mudança coloca valores);

final

Claro, esta simplicidade só agrava a situação: quanto mais simples o algoritmo, mais ela se manifesta todas as falhas. taxa de investimento de tempo é muito grande mesmo para uma pequena array (aqui vem na relatividade: A quantidade de tempo para o leigo pode parecer pequena, mas na verdade um programador cada segundo ou mesmo milissegundo conta).

Levou a melhor implementação. Por exemplo, tendo em conta a troca de valores em locais de matriz:

procedimento Sortirovka_Puzirkom;

começo

sortirovka = true;

ciclo até sortirovka = true;

sortirovka = false;

ciclo para i de nachalnii_index para konechii_index-1;

se massiv [i]> massiv [i + 1] (primeiro elemento maior do que um segundo), então:

(Alterar elementos locais);

sortirovka = true; (Identificado que a troca foi feita).

End.

limitações

A desvantagem principal – a duração do processo. Quanto tempo é realizada algoritmo de ordenação bolha?

tempo de avanço é calculado a partir do número de números de quadrados na matriz – o resultado final é proporcional.

Se o pior caso a matriz é passado tantas vezes quanto ele tem elementos menos um valor. Isso acontece porque no final não é apenas um elemento, que não têm nada para comparar, e o último passe através da matriz se torna ação inútil.

Além disso, o método eficaz de triagem uma troca simples, como é chamado, apenas para matrizes de tamanho pequeno. Grandes quantidades de dados com a ajuda de processo não vai funcionar: o resultado vai ser um erro ou falha do programa.

dignidade

bubble sort é muito fácil de entender. Os currículos das universidades técnicas no estudo dos elementos de ordenação de sua variedade passar em primeiro lugar. O método é fácil de implementar tanto a linguagem Delphi de programação (L (Delphi), e do C / C ++ (C / C plus plus), um incrivelmente simples valores de algoritmo de localização na ordem certa e no Pascal (Pascal). Bubble sort é ideal para iniciantes.

Devido às desvantagens do algoritmo não é usado em fins extracurriculares.

princípio de classificação Visual

A vista inicial da matriz 8 22 4 74 44 37 1 7

Passo 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

Passo 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

Passo 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

Passo 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

Passo 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

Passo 1 4 6 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Passo 7 1 4 7 8 22 37 44 74

exemplo bubble sort em Pascal

exemplo:

kol_mas const = 10;

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

a, b, k: número inteiro;

começar

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

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

para um: = 1 a kol_mas-1 faz começar

para b: = a + 1 a kol_mas começarem

se massiv [a]> massiv [ b] então começar

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

acabar;

acabar;

acabar;

writeln ( 'após tipo');

para um: = 1 a kol_mas fazer writeln (massiv [a ]);

fim.

EXEMPLO bolha triagem em linguagem 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] <massiv [i- 1]) {

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

ff ++;

}

}

se (ff == 0) quebrar;

}

getch (); // atraso de exibição

return 0;

}.