Postoji priličan broj algoritama za sortiranje, mnogi od njih su vrlo specifični i razvijeni su za rješavanje uskog raspona problema i rad sa specifičnim tipovima podataka. Ali među svom ovom raznolikošću, najjednostavniji algoritam je zasluženo mjehurić, koji se može implementirati u bilo kojem programskom jeziku. Uprkos svojoj jednostavnosti, on je u osnovi mnogih prilično složenih algoritama. Još jedna jednako važna prednost je njegova jednostavnost, pa se stoga može zapamtiti i realizirati odmah, bez dodatne literature pred očima.
Uvod
Čitav savremeni Internet je ogroman broj različitih vrsta struktura podataka prikupljenih u bazama podataka. Oni čuvaju sve vrste informacija, od ličnih podataka korisnika do semantičkog jezgra visoko inteligentnih automatizovanih sistema. Nepotrebno je reći da sortiranje podataka igra izuzetno važnu ulogu u ovoj ogromnoj količini strukturiranih informacija. Sortiranje može biti obavezan korak prije traženja bilo kakve informacije u bazi podataka, a poznavanje algoritama za sortiranje izuzetno je važno u programiranju. Postoji priličan broj algoritama za sortiranje, mnogi od njih su vrlo specifični i razvijeni su za rješavanje uskog raspona problema i rad sa specifičnim tipovima podataka. Ali među svom ovom raznolikošću, najjednostavniji algoritam je zasluženo bubble sort koji se može implementirati u bilo kojem programskom jeziku. Uprkos svojoj jednostavnosti, on je u osnovi mnogih prilično složenih algoritama. Još jedna jednako važna prednost je njegova jednostavnost, pa se stoga može zapamtiti i realizirati odmah, bez dodatne literature pred očima.Sortiranje kroz mašinske i ljudske oči
Zamislimo da želite sortirati 5 kolona različitih visina uzlaznim redoslijedom. Ove kolone se mogu shvatiti kao bilo koja informacija (cijene akcija, propusni opseg komunikacionog kanala, itd.), možete predstaviti svoju verziju ovog problema kako biste ga učinili jasnijim. Pa, kao primjer, razvrstaćemo osvetnike po visini:Za razliku od kompjuterskog programa, sortiranje vam neće biti teško, jer ste u mogućnosti da vidite cijelu sliku i odmah možete shvatiti na kojeg junaka trebate preći kako bi sortiranje po visini bilo uspješno. Vjerovatno ste već pogodili da je za sortiranje ove strukture podataka u rastućem redoslijedu dovoljno zamijeniti mjesta Hulka i Iron Mana:
Gotovo!
I na tome će sortiranje biti uspješno završeno. Međutim, računarska mašina je, za razliku od vas, pomalo glupa i ne vidi celu strukturu podataka u celini. Njegov kontrolni program može usporediti samo dvije vrijednosti u isto vrijeme. Da bi riješila ovaj problem, ona mora unijeti dva broja u svoju memoriju i izvršiti operaciju poređenja na njima, zatim prijeći na drugi par brojeva, i tako sve dok se svi podaci ne analiziraju. Stoga se svaki algoritam sortiranja može vrlo pojednostaviti u tri koraka:- Uporedite dvije stavke;
- Zamijenite ili kopirajte jedan od njih;
- Prelazak na sljedeću stavku;
Algoritam sortiranja mehurića
Bubble sortiranje se smatra najjednostavnijim, ali prije nego što opišemo ovaj algoritam, zamislimo kako biste sortirali osvetnike po visini kada biste mogli, poput mašine, upoređivati samo dva heroja istovremeno. Najvjerovatnije biste uradili (na najoptimalniji način) na sljedeći način:- Prelazite na nulti element našeg niza (Crna udovica);
- Uporedite nulti element (Crna udovica) sa prvim (Hulk);
- Ako je element na nultoj poziciji viši, mijenjate ih;
- U suprotnom, ako je element na nulti poziciji manje, ostavljate ih na njihovim mjestima;
- Pomaknite se na poziciju udesno i ponovite poređenje (uporedite Hulka sa Kapetanom)
Nakon što prođete kroz cijelu listu s takvim algoritmom u jednom prolazu, sortiranje se neće izvršiti u potpunosti. Ali s druge strane, najveća stavka na listi će biti pomjerena na krajnju desnu poziciju. To će se uvijek dešavati, jer čim pronađete najveći element, stalno ćete ga mijenjati dok ga ne pomjerite do samog kraja. Odnosno, čim program "pronađe" Hulka u nizu, pomjerit će ga dalje na sam kraj liste:
Zbog toga se ovaj algoritam zove sortiranje mehurića, jer se kao rezultat njegovog rada najveći element na listi nalazi na samom vrhu niza, a svi manji elementi će biti pomereni za jednu poziciju ulevo:
Da biste završili sortiranje, moraćete da se vratite na početak niza i ponovite gore navedenih pet koraka još jednom, ponovo se pomerajući s leva na desno, poredeći i pomerajući elemente po potrebi. Ali ovaj put morate zaustaviti algoritam jedan element prije kraja niza, jer već znamo da je najveći element (Hulk) tačno na krajnjoj desnoj poziciji:
Dakle, program mora imati dvije petlje. Radi veće jasnoće, prije nego što pređemo na pregled programskog koda, slijedite ovaj link da vidite vizualizaciju operacije sortiranja oblačićima: Vizualizacija operacije sortiranja oblačićima
Implementacija Bubble Sortiranja u Javi
Da biste demonstrirali kako sortiranje funkcionira u Javi, evo programskog koda koji:- kreira niz sa 5 elemenata;
- unosi u njega rast osvetnika;
- prikazuje sadržaj niza;
- implementira mehurasto sortiranje;
- ponovo prikazuje sortirani niz.
- into - metoda za umetanje elemenata u niz;
- štampač - prikazuje sadržaj niza red po red;
bubbleSorter - koji obavlja glavni posao i sortira podatke pohranjene u nizu, ponovo ć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++ ) { // Unutrašnja petlja ako (a [in]> a [in + 1]) // Ako redoslijed elemenata nije u redu toSwap (in, in + 1); // pozivamo metodu koja zamjenjuje mjesta } } }
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, sadržaj iz privremene varijable se upisuje u drugi broj. Ovo je standardna tehnika za zamjenu dva elementa;
i na kraju glavna metoda:
Zaključak
Algoritam sortiranja mehurića jedan je od najsporijih. Ako se niz sastoji od N elemenata, tada će se na prvom prolazu izvršiti N-1 poređenja, na drugom N-2, zatim N-3, itd. Odnosno, ukupno će se proizvesti sljedeće propusnice: (N-1) + (N-2) + (N-3) +… + 1 = N x (N-1) / 2 Dakle, prilikom sortiranja, algoritam izvodi oko 0,5x (N ^ 2) poređenja. Za N = 5, broj poređenja će biti približno 10, za N = 10 broj poređenja će porasti na 45. Dakle, s povećanjem broja elemenata, složenost sortiranja značajno raste:Na brzinu algoritma utiče ne samo broj prolaza, već i broj permutacija koje je potrebno izvršiti. Za slučajne podatke, broj permutacija u prosjeku je (N ^ 2) / 4, odnosno oko polovine 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 inicijalno sortirani obrnutim redoslijedom. Unatoč činjenici da je ovo prilično spor algoritam za sortiranje, 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 osnovu njega izmišljaju se složeni hibridni algoritmi. Ali danas ne govorimo o tome brzo sortiranje, ali o drugom načinu razmjene - starom dobrom bubble sort i njegova poboljšanja, modifikacije, mutacije i varijeteti.
Praktičan izduv iz ovih metoda nije toliko vruć, a mnogi korisnici habrapa su sve ovo prošli u prvoj klasi. 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 pričati o najjednostavnijem razmjene sortiranja.
Ako je neko zainteresovan, reći ću da ima i drugih časova - selekcija sort, sortirati po umetcima, sortiranje spajanjem, sortiranje distribucije, hibridne sorte i paralelne vrste... Usput, ima ih još ezoterična sortiranja... To su razni lažni, u osnovi neostvarivi, komični i drugi pseudoalgoritmi, o kojima ću jednog dana napisati par članaka u IT-humor hub-u.
Ali ovo nema veze sa današnjim predavanjem, sada nas zanima samo jednostavno sortiranje po razmjenama. Ima i dosta samih razmjena (znam ih više od deset), pa ćemo razmotriti tzv. bubble sort i neke druge s tim usko povezane.
Unaprijed ću vas upozoriti da su gotovo sve gore 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 razlog da se članak zatrpa implementacijama na bilo kojem programskom jeziku. Zainteresovani mogu lako pronaći primjere koda na Rosetti, Wikipediji ili bilo gdje drugdje.
Ali da se vratimo na sortiranje razmene. Redosled se javlja kao rezultat višestrukog sekvencijalnog nabrajanja niza i međusobnog poređenja parova elemenata. Ako upoređeni elementi nisu poređani jedan u odnosu na drugi, onda ih mijenjamo. Pitanje je samo kako tačno zaobići niz i po kom principu odabrati parove za poređenje.
Počnimo ne sa referentnim sortiranjem oblačića, već s algoritmom koji se zove ...
Glupo sortiranje
Sortiranje je stvarno glupo. Prelazimo niz s lijeva na desno i usput uspoređujemo susjede. Ako naiđemo na par međusobno nesortiranih elemenata, onda ih zamjenjujemo i vraćamo se na početak, odnosno na sam početak. Ponovo prolazimo kroz njega i proveravamo niz, ako ponovo sretnemo „pogrešan“ par susednih elemenata, onda menjamo mesta i počinjemo iznova. Nastavljamo sve dok se niz polako ne sredi.“Znači svaka budala zna kako da sortira” - kažete i bićete potpuno u pravu. Zato se sortiranje naziva „glupo“. U ovom predavanju ćemo dosljedno poboljšavati i modificirati ovu metodu. Sada ima privremene poteškoće O(n 3), nakon što smo napravili jednu ispravku, već smo doveli do O(n 2), onda ćemo još malo ubrzati, pa još, i na kraju ćemo dobiti O(n log n) - i to uopće neće biti "Brzo sortiranje"!
Hajde da napravimo jedno poboljšanje u glupoj vrsti. Nakon što smo tokom šetnje pronašli dva susjedna nesortirana 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 ...
Bubble sort
Or sortiranje jednostavnim razmjenama... Besmrtni klasik žanra. Princip djelovanja je jednostavan: prolazimo kroz niz od početka do kraja, istovremeno mijenjajući mjesta nesortiranih susjednih elemenata. Kao rezultat prvog prolaza, maksimalni element će "iskočiti" na posljednje mjesto. Sada ponovo prolazimo kroz nesortirani dio niza (od prvog do pretposljednjeg) i usput mijenjamo nesortirane susjede. Drugi najveći element biće na pretposljednjem mjestu. Nastavljajući u istom duhu, zaobići ćemo sve opadajući nesortirani dio niza, gurajući pronađene maksimume do kraja.Ako ne samo da pomjerimo vrhunce do kraja, već i padove pomjerimo na početak, onda ćemo dobiti ...
Shaker sortiranje
Ona je shuffle sort, 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, već minimum. Nakon što smo sortirali prvi i posljednji element u nizu, ponovo 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 mjehurića, budući da se i visoki i najniži naizmjenično migriraju duž niza u traženim smjerovima. Poboljšanja su, kako kažu, evidentna.
Kao što vidite, ako budete kreativni sa procesom nabrajanja, onda je izbacivanje teških (lakih) elemenata na krajeve niza brže. Stoga su majstori predložili još jednu nestandardnu "mapu puta" kako bi se zaobišla lista.
Neparno-parno sortiranje
Ovog puta nećemo juriti napred-nazad kroz niz, već se opet vraćamo ideji sistematskog prelaska s lijeva na desno, već samo širimo korak. Na prvom prolazu, elementi sa neparnim ključem se porede sa susedima na parnim mestima (uporedite 1. sa 2., zatim 3. sa 4., 5. sa 6. i tako dalje). Zatim, naprotiv, upoređujemo / mijenjamo "parne" elemente sa "neparnim". Onda opet "parno-parno", pa opet "parno-neparno". Proces se zaustavlja kada se, nakon dva uzastopna prolaska kroz niz ("parno-parno" i "parno-neparno"), nije dogodila nijedna razmjena. Pa su to riješili.U običnom „mjehuru“, tokom svakog prolaza, sistematski 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 jednom pokretanju. Na ovaj način ispada brže.
Hajde da analiziramo ovo drugo smanjena* za Sortuvannya Bulbashkoy** - Sortuvannya kombajni***. Ova metoda se naručuje vrlo brzo, O(n 2) Njegova najgora složenost. U prosjeku tokom vremena imamo O(n log n), pa čak i najbolje, nećete vjerovati, O(n). Odnosno, vrlo dostojan konkurent svim "brzima" i to, imajte na umu, bez upotrebe rekurzije. Međutim, obećao sam da danas nećemo ulaziti dublje u brzine krstarenja, pustiti to tiho i ići direktno na algoritam.
Za sve su krive kornjače
Malo pozadine. Godine 1980, Wlodzimierz Dobosievich je objasnio zašto sortiranje mehurića i njegovi derivati rade tako sporo. Sve je to zbog kornjača... Kornjače su male stavke na kraju liste. Kao što ste možda primijetili, vrste mehurića su fokusirane na "zečeve" (ne treba ih brkati sa Babuškinovim "zečevima") - velike stavke na vrhu liste. Vrlo brzo se kreću do cilja. Ali spori gmizavci nevoljko puze do početka. Možete prilagoditi "tortilje" koristeći četke za kosu.slika: guilty kornjača
Sortiranje češljem
U "bubble", "shaker" i "parno-odd", kada se ponavlja niz niz, upoređuju se susjedni elementi. Glavna ideja "češlja" je da se u početku uzme dovoljno velika udaljenost između upoređenih elemenata i, kako je niz redosled, suzi ovu udaljenost na minimum. Tako nekako češljamo niz, postepeno ga zaglađujući u sve urednije pramenove.Bolje je uzeti početni jaz između upoređ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 sa faktor smanjenja(rezultat je prirodno zaokružen na najbliži cijeli broj). Zatim, nakon što prođemo niz ovim korakom, ponovo dijelimo korak sa faktor smanjenja i ponovo prođite kroz listu. To se nastavlja sve dok razlika između indeksa ne dostigne jedan. U ovom slučaju, niz se sortira običnim balončićem.
Optimalna vrijednost je utvrđena 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. Deceniju kasnije, kada je programiranje prestalo da bude deo naučnika i inženjera u IBM-u, i kada je već lavinasto dobijalo masovni karakter, metod su ponovo otkrili, istražili i popularizovali 1991. Stephen Lacey i Richard Box.
To je zapravo sve što sam želio da vam kažem o bubble sorti i drugima sličnima.
- Bilješke
* smanjen ( ukr.) - poboljšanje
** Sortuvannya bulbashkoy ( ukr.) - Bubble Sort
*** Sortuvannya kombinator ( ukr.) - Sortiranje češljem
Kada radite sa nizovima podataka, nije neuobičajeno da to rade sortiranje uzlaznim ili silaznim redom, tj. racionalizacija... To znači da elementi istog niza moraju biti raspoređeni striktno po redu. Na primjer, u slučaju rastućeg reda, prethodni element mora biti manji od (ili jednak) sljedećem.
Rješenje
Postoji mnogo metoda sortiranja. Neki od njih su efikasniji, drugi su lakše razumljivi. Sortiranje je dovoljno lako za razumjeti. mehurasta metoda takođe pozvan jednostavnom zamjenom... Šta je to i zašto ima tako čudno ime: "metoda mjehurića"?
Kao što znate, vazduh je lakši od vode, pa mjehurići zraka plutaju. Ovo je samo analogija. U sortiranju mehurića u rastućem redosledu, lakši (sa nižom vrednošću) elementi postepeno "lebde" na početak niza, dok se teži jedan za drugim spuštaju na dno (do kraja niza).
Algoritam i karakteristike ovog sortiranja su kako slijedi:
- Prilikom prvog prolaska kroz niz, elementi se porede u parovima: prvi sa drugim, zatim drugi sa trećim, zatim treći sa četvrtim itd. Ako je prethodni element veći od sljedećeg, oni se zamjenjuju.
- Nije teško pretpostaviti da postepeno najveći broj postaje posljednji. Ostatak niza ostaje nesortiran, iako se primećuje izvesno pomeranje elemenata sa nižom vrednošću na početak niza.
- U drugom prolazu nema potrebe da se poslednji element poredi sa predzadnjim. Poslednji element je već postavljen. To znači da će broj poređenja biti jedan manji.
- Na trećem prolazu više nije potrebno porediti pretposljednji i treći element s kraja. Stoga će broj poređenja biti dva manji nego u prvom prolazu.
- Na kraju krajeva, kada hodate kroz niz, kada su ostala samo dva elementa za poređenje, izvodi se samo jedno poređenje.
- 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.
- Broj poređenja u svakom prolazu je m-i, gdje je i broj prolaza kroz niz (prvi, drugi, treći, itd.).
- Prilikom razmjene elemenata niza obično se koristi "bafer" (treća) varijabla 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; pisati ( "Izvorni niz: "); za i: = 1 do m početi arr [i]: = nasumično (256); pisati (arr [i]: 4); kraj; writeln; writeln; za i: = 1 do m- 1 uradi za j: = 1 do m- i uradim ako arr [j]> arr [j + 1] onda počinje k: = arr [j]; arr [j]: = arr [j + 1]; arr [j + 1]: = k kraj; pisati ( "Sortirani niz:"); za i: = 1 do m zapisati (arr [i]: 4); writeln; readln end.
Ne samo da se ne smatra najbržim metodom, već i zatvara listu najsporijih metoda naručivanja. Međutim, to ima i svojih prednosti. Dakle, sortiranje metodom mjehurića 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 je skovan koristeći analogiju s mjehurićima zraka u vodi. Ovo je metafora. Kao što se mali mjehurići zraka dižu prema gore – na kraju krajeva, njihova gustina je veća od bilo koje tekućine (u ovom slučaju vode), tako i svaki element niza, što je manji po vrijednosti, to se sve više probija do početka liste brojeva.
Opis algoritma
Razvrstavanje mehurića se vrši na sljedeći način:
- prvi prolaz: elementi niza brojeva uzimaju se po dva i takođe se porede 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 haotičnom poretku i još uvijek zahtijevaju sortiranje;
- stoga je neophodan drugi prolaz: napravljen je po analogiji s prethodnim (već opisanim) i ima broj poređenja - minus jedan;
- prolaz broj tri ima jedno manje poređenja od drugog, a dva manje od prvog. Itd;
- da rezimiramo, svaki prolaz ima (ukupne vrijednosti u nizu, određeni broj) minus (broj prolaza) poređenja.
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 razmenjuje elemente niza koji su pogrešno locirani jedan u odnosu na drugi.
Pseudokod baziran na opisanom algoritmu
Najjednostavnija implementacija je sljedeća:
Procedura Sortirovka_Puzirkom;
Počni
ciklus za j od nachalnii_index prije konechii_index;
ciklus za i od nachalnii_index prije konechii_index-1;
ako masiv [i]> masiv
(mijenjajte vrijednosti na mjestima);
Kraj
Naravno, jednostavnost ovdje samo pogoršava situaciju: što je algoritam jednostavniji, više se u njemu pojavljuju svi nedostaci. Cena vremena je previsoka čak i za mali niz (ovde 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:
Procedura Sortirovka_Puzirkom;
Počni
sortirovka = istina;
ciklus zbogom sortirovka = istina;
sortirovka = false;
ciklus za i od nachalnii_index prije konechii_index-1;
ako masiv [i]> masiv(prvi element je veći od drugog), tada:
(menjamo elemente na mestima);
sortirovka = istina; (označava da je razmjena izvršena).
Kraj.
Nedostaci metode
Glavni nedostatak je trajanje procesa. Koliko dugo traje balon?
Vrijeme izvršenja se izračunava iz kvadrata broja brojeva u nizu - konačni rezultat je proporcionalan tome.
U najgorem slučaju, niz će se preć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 akcija.
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 greške ili neuspjeh programa.
Dostojanstvo
Bubble sortiranje je vrlo lako za razumjeti. U nastavnim planovima i programima tehničkih univerziteta, kada se proučava redoslijed elemenata niza, on je prvi koji prolazi. Metoda se lako implementira i u programskom jeziku Delphi (D (Delphi) i u C / C ++ (C / C plus plus), nevjerovatno 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 vannastavne svrhe.
Jasan princip 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
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ćima u Pascalu
primjer:
const kol_mas = 10;
var massiv: niz cijelih brojeva;
a, b, k: cijeli broj;
writeln ("input", 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čnite
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 mehurića u C (C)
#include
#include
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) {
swap (masiv [i], masiv);
if (ff == 0) prekid;
gettch (); // kašnjenje ekrana
Danas ćemo se dotaknuti teme sortiranja u Pascalu. Postoji mnogo različitih metoda, većina njih nije široko poznata i poznavanje njih, u principu, nije potrebno. Dovoljno je poznavati osnovni set i nekoliko dodatnih. U ovom članku ću vas upoznati sa najpoznatijom sortom - bubble sortiranjem, koja se naziva i jednostavna razmjena.
Prvo, šta je Pascal sortiranje i zašto je potrebno? Sortiranje je metoda za namještanje niza (obično u rastućem ili opadajućem redoslijedu). 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 mehurića. Zašto je tako nazvana? Poenta je da je ovo analogija. Zamislite pravilan niz raspoređen okomito. Sortiranje pomera manje stavke prema gore. Odnosno, 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. Suština algoritma je poređenje dva elementa. Tacno dva. Dozvolite mi da objasnim, na primjer, imamo niz sa 10 elemenata. Stavke će se porediti u parovima: 1 i 2, 2 i 3.3 i 4.4 i 5.6 i 7 itd. Prilikom upoređ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, onda će ih zamijeniti.
3. Razvrstavanje mehurića podijeljeno je na korake. U svakom koraku vrši se poređenje u paru. Kao rezultat svakog koraka, najveći elementi počinju da se redaju od kraja niza. To jest, nakon prvog koraka, najveći element niza će biti na posljednjem mjestu. U drugom koraku se radi sa svim elementima osim sa zadnjim. Opet, najveći element se nalazi i stavlja na kraj niza s kojim se rad izvodi. Treći korak ponavlja drugi i tako dalje dok se niz ne sortira. Za praktičniju percepciju, dat ću primjer. Uzmimo niz sa 7 elemenata: 2,5,11,1,7,8,3. Gledamo.(Kliknite na sliku za uvećanje slike)
Idemo direktno 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 do
pročitaj (msort [i]);
Za i: = 1 do m - 1 do
za j: = 1 do m - ja
ako msort [j]> msort onda počni
k: = msort [j];
msort [j]: = msort;
msort: = k;
kraj;
Write ("Sortirani niz:");
za i: = 1 do m do
pisati (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 metodom mjehurića, sljedeći članci će biti objavljeni u narednih sedmica (a možda i ranije).
