Mjehurić sortiranje jednodimenzionalnog polja: algoritam, programski kod na C jeziku

U radu s informacijama najprofitabilniji načini pohranjivanja su strukture i polja. Potonji mogu sadržavati sve one vrste podataka, što je prikladno za korištenje u radu programa. Često se koriste u radu online trgovina i u razvoju igara. Stoga se podaci koji se nalaze u njima se redovito razvrstavaju i zamjenjuju, a na njih se obavljaju logički ili matematički postupci. Jedan od načina za dovođenje reda u polje je sortiranje mjehurića. Ova će publikacija proučavati svoj C kod i logiku permutacija.

Array Sort algoritam

Tehničke poteškoće za programere nisu mjehur sortiranje jednodimenzionalnog polja, iako se vrlo rijetko koristi zbog niske učinkovitosti. Često se razmatra na fazi osposobljavanja kao najjednostavniju. Međutim, daleko je od najučinkovitijih. Njegov algoritam sastoji se naizmjenično uspoređivanje znamenki i međusobno prepisivanjem stanica ako je uvjet ispunjen.

Opis koraka po korak

Na prvoj iteraciji, dva susjedna broja postupno se uspoređuju. Ako je lijevi dio veći, tada se ponovno mijenja s desne strane. Minus 8 i 0 uvjeti ne zadovoljavaju. Zato se na mjestima ne mijenjaju. Zero i 5 također se ne uklapaju. 5 i 3 su prikladni. Međutim, na ovoj iteraciji okvir za čitanje ne pada na prvih pet, ali se prebacuje udesno, od 5. prije nego što je to uspoređeno s nultom. To znači da se sljedeći par - 3 i 9. mijenja mjesta, a zatim čitatelju ponuđeno je da pregledaju sve zamjene neovisno bez autorovih komentara i da prouče algoritam sortiranja mjehurića.

Kao rezultat svih ponavljanja postupno razvrstanih polje, a to se događa uglavnom kako slijedi: veliki pozitivni brojevi brzo pomak u desno, dok je manji i negativni lijevo polako mijenjaju. Izgleda da se mjehurići plina u tekućini brzo podižu. Zbog te analogije, algoritam se nazivao sortiranje mjehurića.

Procjena računalne složenosti

Idealni algoritam razvrstavanja trebao bi biti što brže moguće. Istodobno, trebalo bi zauzeti malu količinu CPU i memorijskih resursa. I takav proces kao razvrstavanje mjehurića u niz ne može biti najviše energetski učinkovit i profitabilan. Zbog široke primjene, nije pronašao. Ako trenutačno ima manje problema s memorijom, tada bi resursi procesora trebali biti zabrinuti. Budući da digitalni sustavi ne mogu biti samo veliki, već veliki, potrošnja računalnih resursa bit će nepredvidiva.

Ako mjehurić vrste, u načelu, da brzo nositi sa stvarima kako bi u relativno malom polju, najveći može biti prekidi zbog prekoračenje sredstava. To znači da će se univerzalna svojstva inherentna algoritmu povrijediti. i sortiranje mjehurića ima kompleksnost N-kvadrata i vrlo je daleko od logaritma N kompleksnosti. Osim toga, rizik neuspjeha u obradi velikog polja povećava šanse gubitka podataka zbog prebrisanih stanica. Puno isplativo u tom smislu bit će sortiranje umetanja ili Shellov algoritam.

Softver kod

Kôd računala za jezik C u nastavku u grafičkoj aplikaciji omogućuje vam obavljanje sortiranja mjehurića. Prikazuje se kao zasebna funkcija nevažeće vrste. Ne vraća nikakve vrijednosti, ali pomoću pokazivača zamjenjuje elemente ovisno o uvjetima razvrstavanja. U ovom slučaju, kod rješava problem sortiranja mjehurića nizova cijelih brojeva uzlaznim redoslijedom.

Da biste izvršili ovu funkciju, korisnik mora stvoriti niz, koji mora biti popunjen potrebnim vrijednostima. To se može obaviti ručno postavljanjem dimenzije i broja elemenata na početku programa. Zatim možete ispuniti polje konstantnim vrijednostima. Druga mogućnost je stvoriti univerzalni program tako da se izgovori veliki jednodimenzionalni niz od 100 elemenata.

Deklaracija i inicijalizacija polja

Navođenjem cijele varijable i dodjeljivanjem vrijednosti očitane od tipkovnice, možete ograničiti broj ćelija koje će se popuniti. Također možete implementirati funkciju unosa elemenata polja od strane korisnika s tipkovnice pomoću funkcije scanf ("% d", " vrijednost). U ovom primjeru "% d" je niz za modifikaciju koji kaže prevoditelju da će cijela vrijednost biti primljena nakon skeniranja. Varijabilna vrijednost će pohraniti vrijednost koja je veličina jednogdimenzionalnog cijelog polja.

Da biste koristili algoritam razvrstavanja, morate dodati naziv polja i njezinu veličinu na funkciju. U situaciji predstavljenoj u grafičkoj aplikaciji, poziv na funkciju sortiranja izgledat će ovako: BubleSort (dataArray, sizeDataArray). Naravno, na kraju retka nakon funkcije trebate staviti točku sa zarezom umjesto razdoblja, kako to zahtijeva sintaksa pravila programa. Dakle, dataArray je naziv polja koji želite sortirati, a veličinaDataArray je njegova veličina.

Prijenos tih parametara u BubleSort () funkcija će dovesti do činjenice da je umjesto SizeArray, kao što se vidi na slici, u stvarnoj programskih operacija se izvodi s sizeDataArray. To također znači da će funkcija BubleSort () koristiti cijeli broj podatakaArray. Isto tako postoji poziv printArrayFunction () funkcija i ArrayIntegerInputFunction (). Prva je odgovorna za ispis, tj. Za izlaz na konzolu elemenata. A drugi je potreban da bi se popunio elementima koje je unio korisnik s tipkovnice.

Ovaj stil programiranja, kada se izolirane operacije vrše u obliku funkcija, značajno povećava čitljivost koda i ubrzava njegov razvoj. U takvom programu, polje se popunjava odvojeno od tipkovnice, otisnute i same vrste mjehurića. Potonji se može koristiti za organiziranje podataka ili kao sekundarna funkcija dizajnirana za pronalaženje minimuma i maksimuma polja.

Umetanje sortiranja

Kod razvrstavanja umetanjem, pretpostavlja se da se svaki element uspoređuje i da je izgrađen niz elemenata koji su već poredani prema stanju. Kao rezultat toga, rezultat svake kasnije usporedbe je traženje ćelije u koju se može postaviti nova vrijednost. Ali umetanje svake od njih izvodi se u već sortiranom dijelu polja.

Takva obrada je brža i ima manje računarske složenosti. C kod prikazan je u grafičkoj aplikaciji.

Također je izvedena kao funkcija u kojoj se naziv polja koji treba naručiti i veličina polja prosljeđuju kao argumenti. Ovdje možete vidjeti koliko je vrsta mjehurića spora. Umetci sličnog rada mnogo su brži i imaju kompaktni kod.