Metode de sortare în programare: sortare după "bule"

Sortarea cu un balon nu este considerată doar cea mai rapidă metodă, ci mai degrabă închide lista celor mai lente moduri de comandă. Cu toate acestea, are și avantajele sale. Deci, sortarea prin metoda bubble este soluția cea mai logică și cea mai naturală a problemei, dacă trebuie să aranjați elementele într-o anumită ordine. O persoană obișnuită, de exemplu, o va folosi manual, pur și simplu prin intuiție.

De unde a venit acest nume neobișnuit?

Numele metodei a fost inventat utilizând o analogie cu bule de aer în apă. Aceasta este o metaforă. La fel cum bulele mici de aer se ridică la vârf - pentru că densitatea lor este mai mare decât orice lichid (în acest caz - apă) și fiecare element al matricei, cu cât este mai mică valoarea, cu atât mai mult devine treptat până la începutul listei de numere.

Descrierea algoritmului

Selectarea cu bule se efectuează după cum urmează:

• Prima trecere: elementele matricei de numere sunt luate în două și sunt, de asemenea, comparate în perechi. Dacă în unele două elemente prima valoare este mai mare decât cea de-a doua, programul face schimbul de locuri;
• Prin urmare, cel mai mare număr este la sfârșitul matricei. În timp ce toate celelalte elemente rămân, așa cum erau, într-o ordine haotică și necesită o sortare suplimentară;
• Prin urmare, este necesară oa doua trecere: se produce prin analogie cu cea anterioară (deja descrisă) și are un număr de comparații - minus unul;
• La trecere, comparațiile de numărul trei sunt una mai mică decât a doua și două decât prima. Și așa mai departe;
• Rezumăm că fiecare trecere are (în serie, un număr specific) minus (număr de pași) comparații.

Chiar și algoritmul mai scurt al viitorului program poate fi scris după cum urmează:

• Gama de numere este verificată până când se găsesc două numere, al doilea dintre ele fiind mai mare decât primul;
• Localizate incorect în raport cu celelalte elemente ale matricei, programul se schimbă.

Pseudocod bazat pe algoritmul descris

Cea mai simplă implementare este după cum urmează:

Procedura Sortirovka_Puzirkom ;

început

O buclă pentru j de la nachalnii_index la konechii_index ;

O buclă pentru i de la nachalnii_index la konechii_index-1 ;

Dacă massiv [i]> massiv [i + 1] (primul element este mai mare decât al doilea), atunci:

(Schimbați valorile în locații);

Sfârșitul

Desigur, aici simplitatea exacerbează situația: cu cât algoritmul este mai simplu, cu atât mai mult arată toate neajunsurile. Consumatoare de timp este prea mare chiar și pentru o serie mică (aici vine relativitatea: pentru persoana medie cantitatea de timp poate părea mică, dar în programator în fiecare secundă sau chiar milisecunde în cont).

A fost nevoie de o implementare mai bună. De exemplu, luând în considerare schimbul de valori în matrice în anumite locuri:

Procedura Sortirovka_Puzirkom ;

început

Sortirovka = adevărat;

Ciclul în timp ce sortirovka = adevărat;

Sortirovka = fals;

O buclă pentru i de la nachalnii_index la konechii_index-1 ;

Dacă massiv [i]> massiv [i + 1] (primul element este mai mare decât al doilea), atunci:

(Schimbăm elementele în locații);

Sortirovka = adevărat; (Indicat că schimbul a fost făcut).

Sfârșitul.

Dezavantaje ale metodei

Principalul dezavantaj este durata procesului. Cât durează algoritmul de sortare a bulei?

Timpul de execuție este calculat din pătratul numărului de numere din matrice - rezultatul final este proporțional cu acesta.

Cu cel mai rău scenariu, matricea va fi traversată de câte ori există elemente în ea, minus o valoare. Acest lucru se datorează faptului că în final există doar un element care nu are nimic de comparat și ultima trecere prin matrice devine o acțiune inutilă.

În plus, metoda de sortare prin simple schimburi, așa cum se mai numește, este eficientă numai pentru rețele de dimensiuni reduse. Cantități mari de date nu pot fi procesate prin utilizarea acestora: rezultatul va fi fie erori, fie un accident de program.

demnitate

Sortarea unui bule este foarte ușor de înțeles. În curricula universităților tehnice, atunci când studiază ordonarea elementelor unei matrice, ea trece mai întâi. Metoda este ușor de implementat atât în limbajul de programare Delphi (D (Delphi) și C / C ++ (C / C plus plus), un algoritm incredibil de simplu pentru aranjarea valorilor în ordinea corectă și pentru Pascal (Pascal) .

Din cauza deficiențelor, algoritmul nu este utilizat în scopuri extrașcolare.

Un principiu clar de sortare

Vederea inițială a matricei este 8 22 4 74 44 37 1 7

Pasul 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

Pasul 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

Pasul 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

Pasul 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

Pasul 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

Pasul 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Pasul 7 1 4 7 8 22 37 44 74

Exemplu de sortare cu un balon în Pascal

exemplu:

Const col_mas = 10;

Var masiv: matrice [1..kol_mas] cu număr întreg;

A, b, k: întreg;

începe

Writeln ("intrare", kol_mas, "elemente de matrice");

Pentru a: = 1 la col_mas do readln (masiv [a]);

Pentru o: = 1 la col_mas-1 începe

Pentru b: = a + 1 la kol_mas nu începe

Dacă massiv [a]> massiv [b] începe apoi

K: = masiv [a]; Massiv [a]: = masiv [b]; Massiv [b]: = k;

se încheie;

se încheie;

se încheie;

Writeln ("după sortare");

Pentru a: = 1 la kol_mas do writeln (masiv [a]);

end.

Exemplu de sortare cu un balon în C (C)

exemplu:

#include

#include

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

{

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

Pentru (;;) {

Ff = 0;

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

Dacă (massiv [i]

Swap (masiv [i], masiv [i-1]);

Ff ++;

}

}

Dacă (ff == 0) se rupe;

}

Getch (); // întârziere ecran

Return 0;

}.