Postoji priličan broj algoritama za razvrstavanje, mnogi od njih su vrlo specifični i razvijeni su za rješavanje uskog raspona problema i rada s određenim tipovima podataka. Ali među svom tom raznolikošću, najjednostavniji algoritam je zasluženo sortiranje mjehurića, koji se može implementirati u bilo kojem programskom jeziku. Unatoč svojoj jednostavnosti, on je temelj mnogih prilično složenih algoritama. Jednako važna prednost je i njegova jednostavnost, pa se stoga može zapamtiti i realizirati odmah, bez dodatne literature pred očima.

Uvod

Cijeli moderni Internet je ogroman broj različitih vrsta struktura podataka prikupljenih u bazama podataka. Pohranjuju sve vrste informacija, od osobnih podataka korisnika do semantičke jezgre visoko inteligentnih automatiziranih sustava. Nepotrebno je reći da sortiranje podataka igra iznimno važnu ulogu u ovoj ogromnoj količini strukturiranih informacija. Razvrstavanje može biti obavezan korak prije traženja bilo kakve informacije u bazi, a poznavanje algoritama razvrstavanja iznimno je važno u programiranju. Postoji priličan broj algoritama za razvrstavanje, mnogi od njih su vrlo specifični i razvijeni su za rješavanje uskog raspona problema i rada s određenim tipovima podataka. Ali među svom tom raznolikošću, najjednostavniji algoritam je zasluženo mjehurić sortiranje koji se može implementirati u bilo kojem programskom jeziku. Unatoč svojoj jednostavnosti, on je temelj mnogih prilično složenih algoritama. Jednako važna prednost je i njegova jednostavnost, pa se stoga može zapamtiti i realizirati odmah, bez dodatne literature pred očima.

Razvrstavanje kroz strojne i ljudske oči

Zamislimo da želite sortirati 5 stupaca različitih visina uzlaznim redoslijedom. Ovi stupci se mogu shvatiti kao bilo koja informacija (cijene dionica, širina komunikacijskog kanala, itd.), možete predstaviti vlastitu verziju ovog problema kako biste ga učinili jasnijim. Pa, kao primjer, razvrstati ćemo osvetnike po visini:

Za razliku od računalnog programa, sortiranje vam neće biti teško, jer možete vidjeti cijelu sliku i odmah možete shvatiti na kojeg junaka trebate prijeći kako bi sortiranje po visini bilo uspješno. Vjerojatno ste već pogodili da je za sortiranje ove strukture podataka uzlaznim redoslijedom dovoljno zamijeniti mjesta Hulka i Iron Mana:

Gotovo!

I na tome će sortiranje biti uspješno završeno. Međutim, računalni stroj, za razliku od vas, pomalo je glup i ne vidi cijelu strukturu podataka u cjelini. Njegov upravljački program može usporediti samo dvije vrijednosti u isto vrijeme. Kako bi riješila ovaj problem, ona mora unijeti dva broja u svoju memoriju i izvršiti operaciju usporedbe na njima, zatim prijeći na drugi par brojeva, i tako sve dok se ne analiziraju svi podaci. Stoga se svaki algoritam sortiranja može vrlo pojednostaviti u tri koraka:

• Usporedite dvije stavke;
• Zamijenite ili kopirajte jedan od njih;
• Prijeđite na sljedeću stavku;

Različiti algoritmi mogu izvoditi ove operacije na različite načine, ali prijeći ćemo na ispitivanje kako funkcionira sortiranje mjehurićima.

Algoritam sortiranja mjehurićima

Razvrstavanje mjehurićima smatra se najjednostavnijim, ali prije nego što opišemo ovaj algoritam, zamislimo kako biste razvrstali osvetnike po visini da možete, poput stroja, uspoređivati ​​samo dva heroja odjednom. Najvjerojatnije biste učinili (na najoptimalniji način) kako slijedi:

• Prelazite na nulti element našeg niza (Crna udovica);
• Usporedite nulti element (Crna udovica) s prvim (Hulk);
• Ako je element na nultom položaju viši, mijenjate ih;
• Inače, ako je element na nultom položaju manje, ostavljate ih na njihovim mjestima;
• Pomaknite se na položaj udesno i ponovite usporedbu (usporedite Hulka s kapetanom)

Nakon što prođete kroz cijeli popis s takvim algoritmom u jednom prolazu, sortiranje se neće izvršiti u potpunosti. No, s druge strane, najveća stavka na popisu bit će pomaknuta na krajnju desnu poziciju. To će se uvijek dogoditi, jer čim pronađete najveći element, stalno ćete ga mijenjati dok ga ne pomaknete do samog kraja. Odnosno, čim program "pronađe" Hulka u nizu, pomaknut će ga dalje na sam kraj popisa:

Zato se ovaj algoritam naziva sortiranje mjehurićima, budući da se kao rezultat njegovog rada najveći element na listi nalazi na samom vrhu niza, a svi manji elementi bit će pomaknuti za jednu poziciju ulijevo:

Da biste dovršili sortiranje, morat ćete se vratiti na početak niza i ponoviti gornjih pet koraka još jednom, ponovno se pomičući s lijeva na desno, uspoređujući i pomičući elemente prema potrebi. Ali ovaj put morate zaustaviti algoritam jedan element prije kraja niza, jer već znamo da je najveći element (Hulk) točno u krajnjem desnom položaju:

Dakle, program mora imati dvije petlje. Radi veće jasnoće, prije nego što prijeđemo na pregled programskog koda, slijedite ovu vezu da biste vidjeli vizualizaciju operacije sortiranja mjehurićima: Vizualizacija operacije sortiranja mjehurićima

Implementacija Bubble Sortiranja u Javi

Da biste pokazali kako sortiranje funkcionira u Javi, evo programskog koda koji:

• stvara niz s 5 elemenata;
• učitava u nju rast osvetnika;
• prikazuje sadržaj niza;
• implementira sortiranje mjehurićima;
• ponovno prikazuje sortirani niz.

Možete provjeriti kod u nastavku, pa čak i prenijeti ga na svoj omiljeni IntelliJ IDE. U nastavku će se raščlaniti: klasa ArrayBubble (privatno dugo a; // referenca na niz privatni int elementi; // broj elemenata u nizu javni ArrayBubble (int max) ( // konstruktor klase a = novo dugo [max]; // stvoriti niz veličine max elems = 0; // kada je kreiran, niz sadrži 0 elemenata) javna praznina u (duga vrijednost) ( // metoda za umetanje elementa u niz a [elems] = vrijednost; // umetnuti vrijednost u niz a elems ++; // veličina polja se povećava) javni nevažeći pisač () ( // metoda za izlaz niza na konzolu za (int i = 0; i< elems; i++ ) { // za svaki element u nizu Sustav. van. ispis (a [i] + ""); // izlaz na konzolu Sustav. van. println (""); // na novom redu) Sustav. van. println ( "---- Kraj izlaza niza ----"); ) private void toSwap (int prvi, int drugi) ( // metoda mijenja nekoliko brojeva niza duga lutka = a [prva]; // stavi prvi element u privremenu varijablu a [prvi] = a [drugi]; // zamijeniti prvi s drugim elementom a [drugi] = lutka; // umjesto drugog elementa upisujemo prvi iz privremene memorije) public void bubbleSorter () (za (int out = elems - 1; out>< out; in++ ) { // Unutarnja petlja if (a [in]> a [in + 1]) toSwap (in, in + 1); )))) javna klasa Main (javni statički void main (String args) (ArrayBubble array = new ArrayBubble (5); // Kreirajte niz od 5 elemenata niz. u (163); // ispuniti niz niz. u (300); niz. u (184); niz. u (191); niz. u (174); niz. pisač (); // prikaz stavki prije sortiranja niz. bubbleSorter (); // KORISTITE SORTIRANJE MJEHURIMA niz. pisač (); // ponovno prikazati sortirani popis)) Unatoč detaljnim komentarima u kodu, dat ćemo opis nekih metoda predstavljenih u programu. Ključne metode koje obavljaju većinu posla u programu napisane su u klasi ArrayBubble. Klasa sadrži konstruktor i nekoliko metoda:

• into - metoda za umetanje elemenata u niz;
• pisač - prikazuje sadržaj niza redak po red;

toSwap - mijenja stavke ako je potrebno. Za to se koristi privremena varijabla dummy u koju se upisuje vrijednost prvog broja, a vrijednost iz drugog broja upisuje se umjesto prvog. Nakon toga se sadržaj iz privremene varijable upisuje na drugi broj. Ovo je standardna tehnika zamjene dvaju elemenata;

i na kraju glavna metoda:

• bubbleSorter - koji obavlja glavni posao i sortira podatke pohranjene u nizu, ponovno ćemo ga dati zasebno:

  public void bubbleSorter () ( // METODA SORTIRANJA MJEHURIMA for (int out = elems - 1; out> = 1; out--) (// Vanjska petlja za (int in = 0; in< out; in++ ) { // Unutarnja petlja ako (a [in]> a [in + 1]) // Ako redoslijed elemenata nije u redu zamijeniti (u, u + 1); // pozvati metodu koja mijenja mjesta } } }

Ovdje treba obratiti pažnju na dva brojača: vanjski izlaz i unutarnji ulaz. Vanjski brojač izlaz počinje ponavljati vrijednosti s kraja niza i postupno se smanjuje sa svakim novim prolazom za jedan. Varijabla out sa svakim novim prolazom pomiče se skroz ulijevo kako ne bi utjecala na vrijednosti koje su već sortirane na desnoj strani niza. Unutarnji brojač počinje ponavljati vrijednosti od početka niza i postupno se povećava za jedan na svakom novom prolazu. U koracima dok ne dosegne (posljednja raščlanjena stavka u trenutnom prolazu). Unutarnja in petlja uspoređuje dvije susjedne ćelije u i u + 1. Ako je u trgovinama veći broj od + 1, poziva se metoda toSwap koja mijenja dva broja.

Zaključak

Algoritam sortiranja mjehurićima jedan je od najsporijih. Ako se niz sastoji od N elemenata, tada će se na prvom prolazu izvršiti usporedbe N-1, na drugom N-2, zatim N-3 itd. To jest, ukupno će se izraditi sljedeće propusnice: (N-1) + (N-2) + (N-3) +… + 1 = N x (N-1) / 2 Dakle, pri sortiranju algoritam izvodi oko 0,5x (N ^ 2) usporedbe. Za N = 5, broj usporedbi bit će približno 10, za N = 10 broj usporedbi će narasti na 45. Dakle, s povećanjem broja elemenata, složenost sortiranja značajno raste:

Na brzinu algoritma ne utječe samo broj prolaza, već i broj permutacija koje je potrebno izvesti. Za slučajne podatke, broj permutacija u prosjeku je (N ^ 2) / 4, odnosno oko polovice broja prolaza. Međutim, u najgorem slučaju, broj permutacija također može biti N ^ 2/2 - to je slučaj ako su podaci u početku sortirani obrnutim redoslijedom. Unatoč činjenici da je ovo prilično spor algoritam sortiranja, vrlo je važno znati i razumjeti kako funkcionira, štoviše, kao što je ranije spomenuto, on je osnova za složenije algoritme. Jgd!

Svi dobro znaju da je najbrža metoda iz klase razmjenskih vrsta tzv brzo sortiranje... O tome pišu disertacije, posvećeni su mu mnogi članci na Habréu, a na temelju njega izmišljaju se složeni hibridni algoritmi. Ali danas ne govorimo o brzo sortiranje, ali o drugoj metodi razmjene - staroj dobroj mjehurić sortiranje i njegova poboljšanja, modifikacije, mutacije i varijeteti.

Praktični ispuh ovih metoda nije toliko vruć, a mnogi korisnici habrapa sve su to prošli u prvom razredu. Stoga je članak namijenjen onima koji su se tek zainteresirali za teoriju algoritama i poduzimaju prve korake u tom smjeru.

slika: mjehurići

Danas ćemo razgovarati o najjednostavnijem razmjene sortiranja.

Ako nekoga zanima, reći ću da postoje i drugi razredi - odabir sortiranje, sortirati po umetcima, razvrstavanje spajanjem, distribucijska sorta, hibridne vrste i paralelne vrste... Usput, ima još ezoterična razvrstavanja... To su razni lažni, u osnovi neostvarivi, komični i drugi pseudoalgoritmi, o kojima ću nekako napisati par članaka u IT-humor hubu.

Ali to nema veze s današnjim predavanjem, sada nas zanima samo jednostavno sortiranje po razmjenama. Ima i dosta samih razmjena razmjene (znam ih više od desetak), pa ćemo razmotriti tzv. mjehurić sortiranje i neke druge s njom usko povezane.

Unaprijed ću vas upozoriti da su gotovo sve navedene metode vrlo spore i da neće biti dublje analize njihove vremenske složenosti. Neki su brži, neki sporiji, ali grubo govoreći, to možemo reći u prosjeku O(n 2). Također, ne vidim razloga za zatrpavanje članka implementacijama na bilo kojem programskom jeziku. Zainteresirani mogu lako pronaći primjere koda na Rosetti, Wikipediji ili bilo gdje drugdje.

No, vratimo se razmjeni sortiranja. Redoslijed se događa kao rezultat višestrukog sekvencijalnog nabrajanja niza i međusobnog uspoređivanja parova elemenata. Ako uspoređeni elementi nisu razvrstani jedan u odnosu na drugi, tada ih mijenjamo. Pitanje je samo kako točno zaobići niz i po kojem principu odabrati parove za usporedbu.

Počnimo ne s referentnim sortiranjem mjehurića, već s algoritmom koji se zove ...

Glupo sortiranje

Razvrstavanje je stvarno glupo. Prelazimo niz s lijeva na desno i usput uspoređujemo susjede. Ako naiđemo na par međusobno nerazvrstanih elemenata, onda ih mijenjamo i vraćamo se na početak, odnosno na sam početak. Ponovno prolazimo kroz nju i provjeravamo niz, ako ponovno sretnemo "pogrešan" par susjednih elemenata, tada mijenjamo mjesta i počinjemo iznova. Nastavljamo dok se niz polako ne sredi.

“Dakle, svaka budala zna kako se razvrstati” - kažete i bit ćete potpuno u pravu. Zato se sortiranje naziva "glupo". U ovom ćemo predavanju dosljedno poboljšavati i modificirati ovu metodu. Sada ima privremene poteškoće O(n 3), nakon što smo napravili jednu korekciju, već smo doveli do O(n 2), onda ćemo još malo ubrzati, pa još i na kraju ćemo dobiti O(n zapisnik n) - i to uopće neće biti "Quick Sort"!

Napravimo samo jedno poboljšanje glupe sorte. Nakon što smo tijekom šetnje pronašli dva susjedna nerazvrstana elementa i zamijenili ih, nećemo se vraćati na početak niza, već ćemo mirno nastaviti hodati do samog kraja.

U ovom slučaju, pred nama nije ništa više od dobro poznatog ...

Razvrstavanje u mjehurićima

Ili sortiranje jednostavnim razmjenama... Besmrtni klasik žanra. Princip djelovanja je jednostavan: prolazimo kroz niz od početka do kraja, istovremeno mijenjajući mjesta nerazvrstanih susjednih elemenata. Kao rezultat prvog prolaza, maksimalni element će "iskočiti" na posljednje mjesto. Sada ponovno prolazimo kroz nesortirani dio niza (od prvog elementa do predzadnjeg) i usput mijenjamo nesortirane susjede. Drugi najveći element bit će na pretposljednjem mjestu. Nastavljajući u istom duhu, zaobići ćemo sve manji nesortirani dio niza, gurajući pronađene maksimume do kraja.

Ako ne samo da pomaknemo vrhunce do kraja, već i pomaknemo niske na početak, onda ćemo dobiti ...

Razvrstavanje shakerom

Ona je promiješaj sortiranje, ona sortiranje koktela... Proces počinje kao u "mjehuru": istiskujemo maksimum do samih dvorišta. Nakon toga skrećemo za 180 0 i idemo u suprotnom smjeru, dok se već kotrljamo na početak, ne maksimum, nego minimum. Nakon što smo razvrstali prvi i zadnji element u nizu, ponovno radimo salto. Nakon što smo nekoliko puta hodali naprijed-natrag, na kraju završavamo proces, nalazeći se u sredini liste.

Shaker sortiranje radi malo brže od sortiranja s mjehurićima, budući da se i visoke i niske vrijednosti naizmjenično migriraju duž niza u traženim smjerovima. Poboljšanja su, kako kažu, evidentna.

Kao što možete vidjeti, ako postanete kreativni s postupkom nabrajanja, onda je izbacivanje teških (lakih) elemenata na krajeve niza brže. Stoga su obrtnici predložili još jednu nestandardnu ​​"kartu puta" kako bi zaobišli popis.

Neparno-parno sortiranje

Ovoga puta nećemo juriti naprijed-natrag kroz niz, već se opet vraćamo ideji sustavnog prelaska s lijeva na desno, već samo širimo korak. Na prvom prolazu elementi s neparnim ključem uspoređuju se sa susjedima na parnim mjestima (usporedite 1. s 2., zatim 3. s 4., 5. sa 6. i tako dalje). Zatim, naprotiv, uspoređujemo / mijenjamo "parne" elemente s "neparnim". Pa opet "par-nepar", pa opet "par-nepar". Proces se zaustavlja kada, nakon dva uzastopna prolaska kroz niz ("parno-parno" i "parno-neparno"), nije izvršena niti jedna razmjena. Pa su to riješili.

U običnom "mjehuriću", tijekom svakog prolaza, sustavno istiskujemo trenutni maksimum do kraja niza. Ako preskočite parne i neparne indekse, tada se svi manje ili više veliki elementi niza istovremeno guraju na jednu desnu poziciju u jednoj vožnji. Na ovaj način ispada brže.

Analizirajmo potonje smanjena* za Sortuvannya Bulbashkoy** - Sortuvannya kombajni***. Ova metoda se naručuje vrlo brzo, O(n 2) Je li njegova najgora složenost. U prosjeku s vremenom imamo O(n zapisnik n), pa čak i najbolje, nećete vjerovati, O(n). To jest, vrlo dostojan konkurent svim "brzima" i to, imajte na umu, bez korištenja rekurzije. Međutim, obećao sam da danas nećemo ulaziti dublje u krstareće brzine, pustiti to tiho i ići izravno na algoritam.

Za sve su krive kornjače

Malo pozadine. 1980. Wlodzimierz Dobosievich je objasnio zašto sortiranje mjehurićima i njegovi derivati ​​rade tako sporo. Sve je to zbog kornjača... Kornjače su male stavke na kraju popisa. Kao što ste možda primijetili, vrste mjehurića usredotočene su na "zečeve" (ne treba ih miješati s Babuškinovim "zečevima") - velike stavke na vrhu popisa. Vrlo žustro kreću do cilja. Ali spori gmazovi nevoljko pužu do početka. Možete prilagoditi "tortilje" koristeći četke za kosu.

slika: kriva kornjača

Razvrstavanje češlja

U "bubble", "shaker" i "parno-odd", kada se ponavlja niz, uspoređuju se susjedni elementi. Glavna ideja "češlja" je u početku uzeti dovoljno veliku udaljenost između uspoređenih elemenata i, kako je niz uređen, suziti tu udaljenost na minimum. Tako nekako češljamo niz, postupno ga zaglađujući u sve urednije pramenove.

Bolje je uzeti početni jaz između uspoređenih elemenata ne bilo kako, već uzimajući u obzir posebnu vrijednost tzv faktor smanjenja, čija je optimalna vrijednost približno 1,247. Prvo, udaljenost između elemenata jednaka je veličini niza podijeljenom s faktor smanjenja(rezultat je prirodno zaokružen na najbliži cijeli broj). Zatim, nakon prolaska kroz niz s ovim korakom, opet dijelimo korak po faktor smanjenja i ponovno prođite kroz popis. To se nastavlja sve dok razlika između indeksa ne dosegne jedan. U ovom slučaju, niz se sortira običnim mjehurićem.

Optimalna vrijednost utvrđena je eksperimentalno i teorijski. faktor smanjenja:

Kada je ova metoda izumljena, malo je ljudi obraćalo pažnju na nju na prijelazu iz 70-ih u 80-e. Desetljeće kasnije, kada je programiranje prestalo biti dio znanstvenika i inženjera u IBM-u, te je već kao lavina dobivalo masovni karakter, metodu su ponovno otkrili, istražili i popularizirali 1991. Stephen Lacey i Richard Box.

To je zapravo sve što sam vam želio reći o mjehurićima i drugima sličnima.

- Bilješke

* smanjen ( ukr.) - poboljšanje
** Sortuvannya bulbashkoy ( ukr.) - Razvrstavanje mjehurićima
*** Kombinator sortiranja ( ukr.) - Razvrstavanje češljem

Prilikom rada s nizovima podataka nije neuobičajeno da to čine sortiranje uzlaznim ili silaznim redoslijedom, t.j. racionalizacija... To znači da elementi istog niza moraju biti raspoređeni strogo po redu. Na primjer, u slučaju uzlaznog reda, prethodni element mora biti manji od (ili jednak) sljedećem.

Riješenje

Postoji mnogo metoda sortiranja. Neki od njih su učinkovitiji, drugi su lakše razumljivi. Razvrstavanje je dovoljno lako razumjeti. metoda mjehurića također zove jednostavnom zamjenom... Što je to i zašto ima tako čudno ime: "metoda mjehurića"?

Kao što znate, zrak je lakši od vode, pa mjehurići zraka plutaju. Ovo je samo analogija. U sortiranju mjehurića uzlaznim redoslijedom, lakši (s nižom vrijednošću) elementi postupno "plutaju" na početak niza, dok se oni teži jedan za drugim spuštaju na dno (do kraja niza).

Algoritam i značajke ovog sortiranja su sljedeći:

1. Tijekom prvog prolaska kroz niz, elementi se uspoređuju u parovima: prvi s drugim, zatim drugi s trećim, zatim treći s četvrtim itd. Ako je prethodni element veći od sljedećeg, oni se zamjenjuju.
2. Nije teško pretpostaviti da postupno najveći broj postaje posljednji. Ostatak niza ostaje nerazvrstan, iako se uočava pomicanje elemenata s nižom vrijednošću na početak niza.
3. Na drugom prolazu nema potrebe uspoređivati ​​zadnji element s predzadnjim. Posljednji element je već na mjestu. To znači da će broj usporedbi biti jedan manji.
4. Na trećem prolazu više nije potrebno uspoređivati ​​pretposljednji i treći element s kraja. Stoga će broj usporedbi biti dva manji nego u prvom prolazu.
5. Uostalom, kada se prolazi kroz niz, kada su ostala samo dva elementa za usporedbu, izvodi se samo jedna usporedba.
6. Nakon toga, prvi element nema s čime usporediti, pa je stoga posljednji prolaz kroz niz nepotreban. Drugim riječima, broj prolaza kroz niz je jednak m-1, gdje je m broj elemenata u nizu.
7. Broj usporedbi u svakom prolazu je m-i, gdje je i broj prolaza kroz niz (prvi, drugi, treći, itd.).
8. Kod razmjene elemenata niza obično se koristi varijabla "buffer" (treća) gdje se privremeno postavlja vrijednost jednog od elemenata.

Pascal program:

konst m = 10; var arr: niz [1 .. m] od cijelog broja; i, j, k: cijeli broj; početi randomizirati; napiši ( "Izvorni niz: "); za i: = 1 do m početi arr [i]: = nasumično (256); napisati (arr [i]: 4); kraj; writeln; writeln; za i: = 1 do m- 1 učiniti za j: = 1 do m- i učiniti ako arr [j]> arr [j + 1] onda počinje k: = arr [j]; arr [j]: = arr [j + 1]; arr [j + 1]: = k kraj; napiši ( "Sortirani niz:"); za i: = 1 do m dopisati (arr [i]: 4); writeln; pročitaj kraj.

Ne samo da se ne smatra najbržom metodom, štoviše, zatvara popis najsporijih metoda naručivanja. Međutim, ima i svojih prednosti. Dakle, razvrstavanje mjehuričkom metodom je najlogičnije i najprirodnije rješenje problema, ako trebate rasporediti elemente određenim redoslijedom. Obična osoba, na primjer, koristit će ga ručno - samo intuicijom.

Otkud ovo neobično ime?

Naziv metode skovan je pomoću analogije s mjehurićima zraka u vodi. Ovo je metafora. Kao što se mali mjehurići zraka dižu prema gore – uostalom, njihova je gustoća veća od bilo koje tekućine (u ovom slučaju, vode), tako i svaki element niza, što je manje vrijednosti, to se postupno probija do početka popisa brojeva.

Opis algoritma

Razvrstavanje mjehurićima radi se na sljedeći način:

• prvi prolaz: elementi niza brojeva uzimaju se po dva i također se uspoređuju u parovima. Ako je u neka dva elementa prva vrijednost veća od druge, program mijenja njihova mjesta;
• dakle, završava na kraju niza. Dok svi ostali elementi ostaju, onakvi kakvi su bili, u kaotičnom redu i još uvijek zahtijevaju sortiranje;
• stoga je drugi prolaz neophodan: napravljen je po analogiji s prethodnim (već opisanim) i ima broj usporedbi - minus jedan;
• prolaz broj tri ima jednu usporedbu manje od druge, a dvije manje od prve. Itd;
• da sumiramo, svaki prolaz ima (ukupne vrijednosti u nizu, određeni broj) minus (broj prolaza) usporedbe.

Još kraće, algoritam budućeg programa može se napisati na sljedeći način:

• niz brojeva se provjerava dok se ne pronađu bilo koja dva broja, a drugi od njih mora biti veći od prvog;
• program izmjenjuje elemente niza koji se neispravno nalaze jedan u odnosu na drugi.

Pseudokod na temelju opisanog algoritma

Najjednostavnija implementacija je sljedeća:

Postupak Sortirovka_Puzirkom;

Početak

ciklus za j iz nachalnii_index prije konechii_index;

ciklus za i iz nachalnii_index prije konechii_index-1;

ako masiv [i]> masiv

(mjestimično promijenite vrijednosti);

Kraj

Naravno, jednostavnost ovdje samo pogoršava situaciju: što je algoritam jednostavniji, više se u njemu pojavljuju svi nedostaci. Trošak vremena je previsok čak i za mali niz (ovdje relativnost dolazi u igru: laiku se količina vremena može činiti malom, ali u poslovanju programera svaka sekunda ili čak milisekunda se računa).

Potrebna je bolja implementacija. Na primjer, uzimajući u obzir razmjenu vrijednosti u nizu po mjestima:

Postupak Sortirovka_Puzirkom;

Početak

sortirovka = istina;

ciklus zbogom sortirovka = istina;

sortirovka = lažno;

ciklus za i iz nachalnii_index prije konechii_index-1;

ako masiv [i]> masiv(prvi element je veći od drugog), tada:

(zamjenjujemo elemente na mjestima);

sortirovka = istina; (označava da je zamjena izvršena).

Kraj.

Nedostaci metode

Glavni nedostatak je trajanje procesa. Koliko dugo traje mjehurić?

Vrijeme izvršenja izračunava se iz kvadrata broja brojeva u nizu – konačni rezultat je proporcionalan tome.

U najgorem slučaju, niz će se prijeći onoliko puta koliko ima elemenata minus jedna vrijednost. To je zato što na kraju ostaje samo jedan element bez ičega za usporedbu, a posljednji prolaz kroz niz postaje beskorisna radnja.

Osim toga, metoda sortiranja jednostavnim razmjenama, kako se još naziva, učinkovita je samo za nizove male veličine. Uz njegovu pomoć neće biti moguće obraditi velike količine podataka: rezultat će biti ili pogreške ili neuspjeh programa.

Dostojanstvo

Razvrstavanje mjehurićima vrlo je lako razumjeti. U nastavnim planovima i programima tehničkih sveučilišta, kada se proučava poredak elemenata niza, prvi prolazi. Metoda se lako implementira i u programskom jeziku Delphi (D (Delphi) i u C / C ++ (C / C plus plus), nevjerojatno jednostavan algoritam za raspoređivanje vrijednosti u ispravnom redoslijedu i u Bubble Sort je idealan za početnike.

Zbog nedostataka algoritam se ne koristi u izvannastavne svrhe.

Jasno načelo sortiranja

Početni pogled na niz 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

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

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ćima u Pascalu

Primjer:

const kol_mas = 10;

var massiv: niz cijelih brojeva;

a, b, k: cijeli broj;

writeln ("ulaz", kol_mas, "elementi niza");

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

za a: = 1 do kol_mas-1 počinje

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

ako masiv [a]> masiv [b] onda počni

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

kraj;

writeln ("nakon sortiranja");

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

Primjer sortiranja mjehurića u C (C)

#uključiti

#uključiti

int main (int argc, char * argv)

int masiv = (36, 697, 73, 82, 68, 12, 183, 88), i, ff;

za (;;) (

ff = 0;

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

ako (masiv [i]< massiv) {

zamijeniti (masiv [i], masiv);

ako (ff == 0) prekid;

dobiti (); // kašnjenje zaslona

Danas ćemo se dotaknuti teme sortiranja u Pascalu. Postoji mnogo različitih metoda, većina njih nije široko poznata, a poznavanje njih, u principu, nije potrebno. Dovoljno je poznavati osnovni set i nekoliko dodatnih. U ovom članku upoznat ću vas s najpoznatijom sortom - bubble sortom, koja se naziva i jednostavna razmjena.
Prvo, što je Pascal sortiranje i zašto je potrebno? Sortiranje je metoda uređenja niza (obično uzlaznim ili silaznim redoslijedom). U zadacima postoje takve linije "rasporedite elemente niza, počevši od minimuma (maksimuma)". Imajte na umu da su to isti.
Vratimo se na sortiranje mjehurića. Zašto je tako nazvana? Poanta je da je ovo analogija. Zamislite pravilan niz raspoređen okomito. Razvrstavanje pomiče manje stavke prema gore. To jest, ovdje se niz može predstaviti u obliku vode, a manji elementi u obliku mjehurića koji plutaju na vrh.

Sada više o samom algoritmu. Sve je prilično jednostavno:
1. Za sortiranje se koriste 2 petlje, jedna ugniježđena u drugu. Jedan se koristi za korake, drugi za pod-korake.
2. Bit algoritma je usporedba dvaju elemenata. Točno dva. Dopustite mi da objasnim, na primjer, imamo niz s 10 elemenata. Stavke će se uspoređivati ​​u parovima: 1 i 2, 2 i 3.3 i 4.4 i 5.6 i 7 itd. Prilikom uspoređivanja parova, ako se prethodni element pokazao više od sljedećeg, oni se zamjenjuju. Na primjer, ako je drugi element 5, a treći 2, oni će ih zamijeniti.
3. Razvrstavanje mjehurićima podijeljeno je u korake. U svakom koraku vrši se usporedba u paru. Kao rezultat svakog koraka, najveći elementi počinju se nizati s kraja niza. To jest, nakon prvog koraka, najveći element niza bit će na posljednjem mjestu. U drugom koraku radi se sa svim elementima osim posljednjeg. Opet se najveći element nalazi i stavlja na kraj niza s kojim se rad izvodi. Treći korak ponavlja drugi i tako sve dok se niz ne sortira. Za prikladniju percepciju, dat ću primjer. Uzmimo niz sa 7 elemenata: 2,5,11,1,7,8,3. Gledamo.(Kliknite na sliku za povećanje slike)

Idemo izravno na kod. Kao što je već spomenuto, potrebne su nam dvije petlje. Ovako će to izgledati

konst
m = 7; (broj elemenata u nizu)

var
msort: niz cijelih brojeva; (zapravo naš niz)
i, j, k: cijeli broj; (i je korak, j je podkorak)

početi
writeln ("Unesite elemente niza");
za i: = 1 do m učiniti
pročitaj (msort [i]);

Za i: = 1 do m - 1 do
za j: = 1 do m - radim
ako msort [j]> msort onda počni
k: = msort [j];
msort [j]: = msort;
msort: = k;
kraj;

Write ("Sortirani niz:");
za i: = 1 do m učiniti
napisati (msort [i]: 4);

kraj.

Obratite pažnju na element k. Potreban je samo za jednu svrhu: zamijeniti dva elementa niza. Činjenica je da u Pascalu ne postoji posebna funkcija koja bi izvršila takvu radnju. Stoga ga morate sami obojiti, dodajući dodatni element za razmjenu. Ovim je članak završen, sortiranjem po metodi mjehurića, sljedeći članci će biti objavljeni u idućih tjedan dana (a možda i ranije).