Razvrsti mehurček enodimenzionalne matrike: algoritem, programska koda v jeziku C

Pri delu z informacijami so najbolj donosni načini za shranjevanje struktur in nizov. Slednji lahko vsebujejo vse vrste podatkov, ki jih je mogoče uporabiti pri delu programa. Pogosto jih uporabljajo pri delu spletnih trgovin in pri razvoju iger. Zato so podatki, ki jih vsebujejo, večkrat razvrščeni in zamenjani ter na njih opravljeni logični ali matematični postopki. Eden od načinov za vnos vrstice v matriko je razvrščanje mehurčkov. Ta publikacija bo preučila svojo kodo C in logiko permutacij.

Algoritem razvrstitve nizov

Tehnične težave za programerja niso mehurčke sortiranje enodimenzionalne matrike, čeprav se zaradi nizke učinkovitosti uporablja zelo redko. Pogostokrat se na stopnji usposabljanja šteje kot najpreprostejši. Vendar pa še zdaleč ni najbolj učinkovita. Njegov algoritem je sestavljen iz izmenično primerjave števk in medsebojno prepihovanje celic, če je izpolnjen pogoj.

Postopek razvrščanja po korakih

Pri prvi ponovitvi se dve sosednji številki postopno primerjata. Če je leva večja, potem je napisana v krajih z desno. Minus 8 in 0 pogoji ne izpolnjujejo. Zato se na mestih ne spreminjajo. Zero in 5 se tudi ne prilegata. 5 in 3 sta primerna. Vendar pa pri tej ponovitvi bralni okvir ne pade na prvih pet, ampak se premakne v desno, saj je 5 pred tem primerjal z ničlo. To pomeni, da se naslednja para - 3 in 9 spremenita. Bralcu se ponudi, da neodvisno pregleduje vse zamenjave brez pripomb avtorja in preuči algoritem razvrščanja mehurčkov.

Zaradi vseh ponovitev je matrika postopoma razvrščena in to je v bistvu primer: velike pozitivne številke se hitro premikajo v desno, manjše in negativne pa se počasi prestavijo na levo. Izgleda, da se mehurčki plina v tekočini hitro dvignejo. Zaradi te analogije je bil algoritem imenovan za razvrščanje mehurčkov.

Ocena kompleksne kompleksnosti

Idealni sortirni algoritem naj bo čim hitrejši. Hkrati bi morala prevzeti majhno količino sredstev CPU in pomnilnika. In takšen postopek kot sortiranje mehurčkov v balonih ne more biti najbolj energetsko učinkovit in donosen. Zaradi široke uporabe ga ni našel. Če trenutno obstaja manj težav s pomnilnikom, je treba skrbeti za procesorske vire. Ker digitalni nizi niso lahko le veliki, ampak ogromni, potem bo poraba računalniških virov nepredvidljiva.

Če razvrščanje mehurčkov načeloma hitro rešuje vzpostavitev reda v sorazmerno majhni matriki, potem lahko v velikem primeru pride do napak zaradi prevelikih stroškov virov. To pomeni, da bo kršena lastnost univerzalnosti, ki je del algoritma. Poleg tega, razvrščanje mehurčkov ima N-kvadratno zapletenost in je zelo daleč od logaritma kompleksnosti N. Poleg tega tveganje neuspeha pri obdelavi velike matrike poveča možnosti izgube podatkov zaradi prepisovanja celic. V zvezi s tem bo veliko bolj donosno sortiranje vstavkov ali Shellov algoritem.

Koda programske opreme

Računalniška koda za jezik C spodaj v grafični aplikaciji vam omogoča, da izvedete razvrščanje mehurčkov. Izvede se kot ločena funkcija tipa neveljavna. Ne vrne nobenih vrednosti, vendar z uporabo kazalcev zamenjamo elemente, odvisno od pogojev razvrščanja. V tem primeru koda rešuje problem razvrščanja mehurčkov v nizu cele številke v naraščajočem vrstnem redu.

Za izvajanje te funkcije mora uporabnik ustvariti matriko, ki mora biti napolnjena z zahtevanimi vrednostmi. To je mogoče storiti ročno, tako da nastavite dimenzijo in število elementov na začetku programa. Potem lahko napolnite matriko s konstantnimi vrednostmi. Druga možnost je ustvariti univerzalni program z razglasitvijo velike enodimenzionalne matrike s 100 elementi.

Objava in inicializacija matrike

Z navedbo celovite spremenljivke in dodeljevanju vrednosti, ki jo berete s tipkovnice, lahko omejite število celic, ki bodo zapolnjene. Lahko tudi izvajate funkcijo vnašanja elementov array s strani uporabnika s tipkovnice z uporabo funkcije scanf ("% d", " vrednost). V tem primeru je "% d" spremenljiv niz, ki pravi prevajalcu, da bo po skeniranju prejeta celostna vrednost. Spremenljiva vrednost bo shranila vrednost, ki je velikost enodimenzionalnega niza integer.

Če želite uporabiti algoritem razvrščanja, morate funkciji dodati ime matrike in njegovo velikost. V situaciji, predstavljeni v grafični aplikaciji, bo klic na funkcijo sortiranja izgledal takole: BubleSort (dataArray, sizeDataArray). Seveda, na koncu vrstice po funkciji, morate namesto obdobja postaviti podpičje, kot zahtevajo sintaksna pravila programa. Torej, dataArray je ime matrike, ki ga želite razvrstiti, in sizeDataArray je njegova velikost.

Prenos teh parametrov v funkcijo BubleSort () bo povzročil, da se operacije izvajajo z velikostjoDataArray namesto uporabe velikostiArray, kot je prikazano na sliki, v pravem programu. To tudi pomeni, da bo funkcija BubleSort () uporabila celoto dataArray. Podobno se kliče funkcija printArrayFunction () in ArrayIntegerInputFunction (). Prvi je odgovoren za tiskanje, to je za izhod na konzolo elementov. In druga je potrebna, da jo izpolnite z elementi, ki jih je uporabnik vnesel s tipkovnice.

Ta stil programiranja, ko se izolirane operacije izvajajo v obliki funkcij, znatno poveča berljivost kode in pospeši njegov razvoj. V takem programu se matrika napolni ločeno od tipkovnice, natisne in sam balon razvrsti. Slednje lahko uporabite za organizacijo podatkov ali kot sekundarno funkcijo, namenjeno najti najmanjšo in najvišjo vrednost matrike.

Razvrščanje vstavkov

Pri sortiranju z vstavljanjem se predpostavlja, da se vsak element primerja po vrsti in zgradi verigo elementov, ki so že razvrščeni glede na stanje. Rezultat vsake poznejše primerjave je iskanje celice, v katero se lahko doda nova vrednost. Ampak vstavitev vsakega od njih se izvaja v že urejenem delu matrike.

Takšna obdelava je hitrejša in ima manj računske kompleksnosti. Koda C je predstavljena v grafični aplikaciji.

Izvaja se tudi kot funkcija, v kateri se ime arrayja, ki ga želite naročiti, in velikost matrike prenesejo kot argumente. Tukaj lahko vidite, kako počasen je mehurček. Vstavi podobno delo veliko hitreje in ima kompaktno kodo.