Načini razvrščanja v programiranju: sortiranje po `bubble`

Sortiranje z mehurčkom se ne šteje le za najhitrejšo metodo, poleg tega pa zapre seznam najpočasnejših 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 želite urediti elemente 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 način prišel, z uporabo analogije zračnih mehurčkov v vodi. To je metafora. Tako kot malo zračni mehurčki dvignejo navzgor -, ker je njihova gostota večja od tekočine (v tem primeru - naj bi pitno vodo), in vsak matrike elementa, manjša je vrednost, bolj postopno pot do vrha številk seznama.

Opis algoritma

Razvrščanje po mehurčku se izvede 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, največje število pade na koncu matrike. Medtem ko vsi ostali elementi ostanejo v kaotičnem zaporedju in zahtevajo nadaljnje razvrščanje;
• zato je potreben drugi prehod: proizveden je po analogiji s prejšnjim (že opisan) in ima številne primerjave - minus eno;
• pri prehodu so tri primerjave ene manj kot druga in dve, kot prva. In tako naprej;
• Naj povzamemo, da ima vsaka prehod (v matriki, določeni številki) primerjalne vrednosti minus (število prelazov).

Še krajši algoritem bodočega programa je lahko napisan takole:

• polje številk se preveri, dokler ne najdemo dveh številk, od katerih mora biti drugi večji od prvega;
• nepravilno nameščeni v povezavi z drugimi elementi v matriki, programske zamenjave.

Pseudocode temelji na opisanem algoritmu

Najenostavnejša izvedba je naslednja:

Postopek Sortirovka_Puzirkom-

Začetek

cikel za j iz nachalnii_index do konechii_index-

cikel za i iz nachalnii_index do konechii_index-1-

če 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 preprost je algoritem, bolj kaže na vse pomanjkljivosti. Naložbe razmerje časa je prevelika celo za majhno paleto (tukaj pride v relativnosti: Čas za navadnega državljana se morda zdi majhen, vendar v resnici programer vsaka sekunda ali celo millisekund fizične osebe).

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

Postopek Sortirovka_Puzirkom-

Začetek

sortirovka = true-

cikel do sortirovka = true-

sortirovka = laži

cikel za i iz nachalnii_index do konechii_index-1-

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

(spreminjamo elemente na mestih) -

sortirovka = true- (označeno je, da je bila izmenjava opravljena).

Konec.

Slabosti metode

Glavna pomanjkljivost je trajanje postopka. Kako dolgo traja? sortirni algoritem mehurček?

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

V najslabšem primeru bo matrika prešla čim večkrat, ker so elementi v njem, minus ena vrednost. To je zato, ker na koncu obstaja samo en element, ki nima ničesar primerjati, in zadnji prehod skozi polje postane neuporabno dejanje.

Poleg tega je metoda razvrščanja 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 ali napake programa.

Prednosti

Sortiranje balona je zelo preprosto razumeti. Kurikulum tehnične univerze v študiji naročanje elementov svojo ponudbo prenese na prvem mestu. Postopek je enostaven za izvajanje tako jezika Delphi programiranje (L (Delphi), in C / C ++ (C / C plus plus), neverjetno preprost vrednosti lokacije algoritma v pravem zaporedju in na Pascal (Pascal). Sortiranje balonov 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

1. korak 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

2. korak 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

3. korak 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

4. korak 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

5. korak 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

6. korak 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 razvrščanja mehurčka v Pascal

Primer:

const kol_mas = 10-

var massiv: array [1..kol_mas] integer-

a, b, k: integer-

začeti

writeln (`input`, kol_mas, `elementi array`) -

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

za a: = 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] - masiv [a]: = masiv [b] - masiv [b]: = k-

end-

end-

end-

pisanje ("po razvrščanju") -

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] < masiv [i-1]) {

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

ff ++ -

}

}

če (ff == 0)

}

getch () - // zakasnitev zaslona

vrnitev 0-

}.