Sortiranje metod v programiranju: razvrščanje po "mehurčku"

Sortiranje po mehurčku se ne šteje le za najhitrejšo metodo, poleg tega pa zapre seznam najbolj počasnih načinov naročanja. Vendar ima tudi svoje prednosti. Torej, razvrščanje po metodi bubble je najbolj logična in naravna rešitev problema, če morate elemente urediti v določenem vrstnem redu. Običajna oseba, na primer, jo bo uporabljala ročno, samo z intuicijo.

Od kje je prišlo to nenavadno ime?

Ime metode smo izumili z analogijo z zračnimi mehurčki v vodi. To je metafora. Prav tako kot se majhni zračni mehurčki dvignejo na vrh - ker je njihova gostota večja od katere koli tekočine (v tem primeru - vode) in vsakega elementa matrike, manjši je v vrednosti, bolj se postopoma pomika na začetek seznama številk.

Opis algoritma

Sortiranje balonov se izvaja na naslednji način:

• Prvi prehod: elementi množice številk se vzamejo v dveh in jih primerjamo tudi v parih. Če je v nekaterih dveh elementih prva vrednost večja od druge, program naredi izmenjavo mest;
• Zato je največje število na koncu matrike. Medtem ko vsi ostali elementi ostanejo v kaotičnem vrstnem redu in zahtevajo nadaljnje razvrščanje;
• Zato je potreben drugi prehod: izdelan je po analogiji s prejšnjim (že opisan) in ima številne primerjave - minus eno;
• Na prehodu so tri primerjave ene manj kot druga, dvojka pa je dvoja od prve. In tako naprej;
• Povzemamo, da ima vsaka prehoda primerjalne (v matriki, določeni številki) minus (število prelazov).

Še krajši algoritem bodočega programa lahko zapišemo na naslednji način:

• Matrika številk se preveri, dokler ne najdemo dveh številk, od katerih mora biti druga večja od prve;
• Nepravilno nameščeni v povezavi z drugimi elementi matrike, se program zamenja.

Pseudocode temelji na opisanem algoritmu

Najenostavnejša izvedba je naslednja:

Postopek Sortirovka_Puzirkom ;

Začni

Zanka za j od nachalnii_index do konechii_index ;

Zanko za i od nachalnii_index do konechii_index-1 ;

Če je masiv [i]> masiv [i + 1] (prvi element je večji od drugega), potem:

(Spremenite vrednosti na mestih);

Konec

Seveda tu preprostost le še poslabša situacijo: bolj enostaven je algoritem, bolj kaže na vse pomanjkljivosti. Dolgotrajno je prevelika tudi za majhno matriko (tu je relativnost: povprečna oseba se lahko zdi majhna, vendar v računalniku vsake sekunde ali celo milisekunde na računu).

Potrebno je bilo bolje izvajati. Na primer, ob upoštevanju izmenjave vrednosti v matriki na nekaterih mestih:

Postopek Sortirovka_Puzirkom ;

Začni

Sortirovka = true;

Cikel, medtem ko sortirovka = true;

Sortirovka = false;

Zanko za i od nachalnii_index do konechii_index-1 ;

Če je masiv [i]> masiv [i + 1] (prvi element je večji od drugega), potem:

(Elemente spremenimo v krajih);

Sortirovka = true; (Navedeno, da je bila izmenjava opravljena).

Konec.

Slabosti metode

Glavna pomanjkljivost je trajanje postopka. Kako dolgo deluje algoritem sortiranja mehurčkov?

Čas izvedbe se izračuna iz kvadrata števila številk v matriki - končni rezultat je sorazmeren zanj.

Z najslabšim možnim scenarijem se array preusmeri čim večkrat, saj so elementi v njem, minus ena vrednost. To je zato, ker na koncu obstaja samo en element, s katerim ni mogoče primerjati, in zadnji prehod skozi polje postane neuporabno dejanje.

Poleg tega je metoda sortiranja s preprostimi izmenjavami, tako kot se tudi imenuje, učinkovita samo za nizke velikosti. Velike količine podatkov ni mogoče obdelati z njo: rezultat je bodisi napake bodisi sesutje programa.

Prednosti

Sortiranje balona je zelo enostavno razumljivo. V učnih načrtih tehničnih univerz, ko preučuje naročanje elementov polja, najprej preide. Metoda se enostavno izvaja tako v programskem jeziku Delphi (D (Delphi) kot C / C ++ (C / C plus plus)), neverjetno enostaven algoritem za urejanje vrednosti v pravilnem zaporedju in za Pascal (Pascal) . Razvrščanje mehurčkov je idealno za začetnike.

Zaradi pomanjkljivosti se algoritem ne uporablja za zunajšolske namene.

Jasno načelo sortiranja

Začetni pogled na matriko je 8 22 4 74 44 37 1 7

Korak 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

Korak 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

Korak 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

Korak 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

Korak 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

Korak 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Korak 7 1 4 7 8 22 37 44 74

Primer sortiranja z mehurčkom v Pascalu

Primer:

Const kol_mas = 10;

Var masiv: array [1..kol_mas] celega števila;

A, b, k: celo število;

Začni

Writeln ('input', kol_mas, 'elementi array');

Za a: = 1 do kol_mas do readln (masiv [a]);

Za: = 1 do kol_mas-1 se začne

Za b: = a + 1 do kol_mas se začne

Če se začne masiv [a]> masiv [b]

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

Konec;

Konec;

Konec;

Writeln ("po razvrstitvi");

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

Konec.

Primer razvrščanja z mehurčkom v C (C)

Primer:

#include

#include

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

{

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

Za (;;) {

Ff = 0;

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

Če (masiv [i]

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

Ff ++;

}

}

Če (ff == 0) zlomite;

}

Getch (); // zakasnitev zaslona

Vrnitev 0;

}.