Razvrstavanje metoda u programiranju: razvrstavanje pomoću "mjehurića"

Razvrstavanje pomoću mjehurića ne samo da se ne smatra najbržom metodom, štoviše, on zatvara popis najsporijih načina naručivanja. Međutim, također ima svoje prednosti. Dakle, razvrstavanje metodom mjehurića je najlogičnije i prirodno rješenje problema, ako želite organizirati elemente u određenoj poruci. Primjerice, obična osoba će ga koristiti rukom, jednostavno intuicijom.

Odakle dolazi taj neobičan naziv?

Ime metode je izumljeno analogno s mjehurićima zraka u vodi. Ovo je metafora. Baš kao mali mjehurići zraka rasti prema gore - jer im je gustoća veća od tekućine (u ovom slučaju - voda), i svaki element matrice, to je vrijednost, postupan način na vrhu popisa brojeva manji.

Opis algoritma

Razvrstavanje prema mjehuriću izvodi se na sljedeći način:

• prvi prolaz: elementi nizova brojeva se uzimaju u dva i uspoređuju se u parovima. Ako je u nekim od dva elementa prva vrijednost veća od drugog, program mijenja razmjenu mjesta;
• dakle, najveći broj pada na kraj polja. Dok svi ostali elementi ostaju, kao oni, u kaotičnom poretku i zahtijevaju daljnje razvrstavanje;
• stoga je potreban drugi prolaz: proizveden je analogijom s prethodnim (već opisanim) i ima niz usporedbi - minus jedan;
• na prolazu, usporedbe broj tri su manje od druge i dvije od prvog. I tako dalje;
• Ukratko, svaki putnik ima (u nizu, određeni broj) minus (broj prolaza) usporedbe.

Čak i kraći algoritam budućeg programa može se napisati na sljedeći način:

• niz brojeva provjerava se dok se ne pronađu dva broja, od kojih drugi mora biti veći od prve;
• nepravilno locirani u odnosu na svaki drugi element polja, program zamjenjuje.

Pseudocode na temelju opisanog algoritma

Najjednostavnija implementacija je sljedeća:

postupak Sortirovka_Puzirkom-

Početak

ciklus za j od nachalnii_index do konechii_index-

ciklus za ja od nachalnii_index do konechii_index-1-

ako masiv [i]> massiv [i + 1] (prvi element veći je od drugog), zatim:

(mijenjajte vrijednosti na mjestima) -

Kraj

Naravno, ovdje jednostavnost samo pogoršava situaciju: što je algoritam jednostavniji, to pokazuje sve nedostatke. Omjer uloženog vremena je prevelika čak i za malu lepezu (ovdje dolazi u relativnosti: Količina vremena za laik može činiti malo, ali u stvari programer svaki drugi ili čak milisekundni broji).

Trebalo je bolje provedbe. Na primjer, uzimajući u obzir razmjenu vrijednosti u nizu na nekim mjestima:

postupak Sortirovka_Puzirkom-

Početak

sortirovka = true-

ciklus do sortirovka = true-

sortirovka = lie-

ciklus za ja od nachalnii_index do konechii_index-1-

ako masiv [i]> massiv [i + 1] (prvi element veći je od drugog), zatim:

(promijenimo elemente na mjestima) -

sortirovka = true- (naznačeno je da je razmjena napravljena).

Kraj.

Nedostaci metode

Glavni nedostatak je trajanje postupka. Koliko vremena je potrebno? algoritam razvrstavanja mjehurić?

Vrijeme izvršenja izračunato je iz kvadrata broja brojeva u polju - konačni rezultat je proporcionalan toj vrijednosti.

S najgorim scenarijem, polje će biti prebačeno onoliko puta koliko ima elemenata u njemu, minus jedna vrijednost. To je zato što na kraju postoji samo jedan element koji nema ničega za usporedbu, a zadnji prolaz kroz polje postaje beskorisno djelovanje.

Osim toga, metoda sortiranja jednostavnim razmjenama, kao što se i naziva, djelotvorna je samo za polja male veličine. Velike količine podataka ne mogu se obrađivati ​​pomoću njega: rezultat će biti pogreške ili neuspjeh programa.

dostojanstvo

Razvrstavanje mjehurića vrlo je razumljivo. U kurikulumu tehničkih sveučilišta, kada proučava naručivanje elemenata polja, prolazi prvo. Metoda se lako provodi i na Delphi programskom jeziku (D (Delphi) i C / C + + (C / C plus plus), nevjerojatno jednostavan algoritam za uređivanje vrijednosti u ispravnom redoslijedu i na Pascal (Pascal). Razvrstavanje mjehurića idealan je za početnike.

Zbog nedostataka, algoritam se ne koristi za izvannastavne svrhe.

Jasno načelo sortiranja

Početni prikaz polja 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

Primjer sortiranja mjehurića u Pascalu

primjer:

const kol_mas = 10-

var masiv: polje [1..kol_mas] od integer-

a, b, k: integer-

početi

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

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

za: = 1 do kol_mas-1 započeti

za b: = a + 1 do kol_mas počinje

ako masiv [a]> massiv [b] potom započne

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

krajnjeg

krajnjeg

krajnjeg

pisati ("poslije sortiranja") -

za: = 1 do kol_mas do writeln (massiv [a]) -

kraj.

Primjer sortiranja mjehurićima u C (C)

primjer:

#include

#include

int glavni (int argc, char * argv [])

{

int masiv [8] = (36, 697, 73, 82, 68, 12, 183, 88), i, f-

za (- -) {

ff = 0-

za (i = 7- i> 0-i-) {

ako (masiv [i] < masiv [i-1]) {

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

ff ++ -

}

}

ako (ff == 0) break-

}

getch () - // kašnjenje zaslona

povrat 0-

}.