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

sortare cu bule, nu este numai considerată a fi cea mai rapidă metodă, în plus, se închide lista celor mai lente metode de organizare. 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ă doriți 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 bulele de aer în apă. Aceasta este o metaforă. La fel ca bule de aer mici crește în sus - pentru că densitatea lor este mai mare decât un fluid (în acest caz - apa), iar fiecare element de matrice, cu cat mai mic este valoarea, modul mai treptată la partea de sus a numerelor de listă.

Descrierea algoritmului

Sortarea după bule este efectuată 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 cade în capătul 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 precedentă (deja descrisă) și are un număr de comparații - minus unu;
• 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;
• Să rezumăm că fiecare trecere are (în serie, un număr specific) minus (numărul de pași) comparații.

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

• seria numerelor este verificată până la găsirea a două numere, a doua dintre ele fiind mai mare decât prima;
• amplasate incorect în raport cu fiecare element al matricei, programul de swap-uri.

Pseudocod bazat pe algoritmul descris

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

procedură Sortirovka_Puzirkom-

Începutul

ciclu pentru j de la nachalnii_index până la konechii_index-

ciclu pentru eu de la nachalnii_index până la konechii_index-1-

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

(modificați valorile în locații) -

Sfârșitul

Desigur, această simplitate agravează doar situația: cel mai simplu algoritm, mai mult se manifestă toate defectele. Raportul de investiții de timp este prea mare chiar și pentru o gamă mică (de aici vine în teoria relativității: Cantitatea de timp pentru nespecialiști poate părea mic, dar, de fapt, un programator în fiecare secundă sau chiar milisecundă contează).

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

procedură Sortirovka_Puzirkom-

Începutul

sortirovka = true-

ciclu până la sortirovka = true-

sortirovka = minciună-

ciclu pentru eu de la nachalnii_index până la konechii_index-1-

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

(schimbăm elementele în locuri) -

sortirovka = true- (indică faptul că schimbul a fost făcut).

Sfârșitul.

Dezavantaje ale metodei

Principalul dezavantaj este durata procesului. Cât durează? algoritmul de sortare o bubble?

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

În cazul celui 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, iar ultima trecere prin matrice devine o acțiune inutilă.

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

demnitate

Sortarea unui bule este foarte simplu 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 limbajul de programare Delphi (L (Delphi), și C / C ++ (C / C, plus, plus), un valori incredibil de simplu de algoritm de locație în ordinea corectă și la Pascal (Pascal). Selectarea cu bule este ideală pentru începători.

Din cauza deficiențelor, algoritmul nu este utilizat în scopuri extra-curriculare.

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 a unui balon în Pascal

exemplu:

const kol_mas = 10-

var masiv: array [1..kol_mas] de integer-

a, b, k: integer-

începe

scriteln (`input`, kol_mas, `elements of array`) -

pentru a: = 1 la kol_mas do readln (masiv [a]) -

pentru a: = 1 pentru a începe col_mas-1

pentru b: = a + 1 pentru a începe col_mas

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

k = masiv [a] - masiv [a]: = masiv [b] - masiv [b]: = k-

finele

finele

finele

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 -> 0 - i -) {

dacă (masiv [i] < masiv [i-1]) {

swap (masiv [i], masiv [i-1]) -

ff ++ -

}

}

dacă (ff == 0)

}

getch () - // întârziere ecran

retur 0-

}.