Bubble vrsta enodimenzionalnega polja: algoritem, programska koda v jeziku C

Pri delu z informacijami so najbolj donosni načini shranjevanja strukture in nizi. Slednji lahko vsebujejo kakršne koli podatke iste vrste, ki so primerni za uporabo pri delu programa. Pogosto se uporabljajo v spletnih trgovinah in pri razvoju iger. Zato so podatki, ki jih vsebujejo, večkrat razvrščeni in spremenjeni, nad njimi se izvajajo logične ali matematične operacije. Eden od načinov za nastavitev vrstnega reda v matriki je razvrščanje. Ta publikacija bo preučila programsko kodo v jeziku C in logiko permutacij.


Algoritem za razvrščanje matrike

Tehnična zapletenost za programerja ne predstavlja razvrščanja mehurčkov enodimenzionalnega niza, čeprav se zaradi nizke učinkovitosti redko uporablja. Pogosteje se obravnava na stopnji učenja kot najenostavnejša. Vendar pa to še zdaleč ni najbolj učinkovito. Njegov algoritem je sestavljen iz zaporedne primerjave števk in vzajemnega prepisovanja celic, če se opazuje stanje.

Opis sortiranja po korakih

Pri prvi ponovitvi se postopoma primerjata dve sosednji številki. Če je leva večja, potem jo prepišemo z desno. Minus 8 in 0 pogoji niso izpolnjeni. Zato se mesta ne spreminjajo. Nič in 5 tudi nista primerna. 5 in 3 - fit. Pri takšni ponovitvi pa bralni okvir ne pade v prvih pet in se premakne v desno, saj je bil 5 primerjan z ničlo. To pomeni, da se spremeni naslednji par mest - 3 in 9. NaprejVse zamenjave so ponujene bralcu, da se pregledajo neodvisno brez komentarjev avtorja in preučijo algoritem razvrščanja mehurčkov.


Kot rezultat vseh iteracij se matrika postopoma razvrsti in to se zgodi predvsem na naslednji način: velika pozitivna števila se hitro premaknejo v desno, manjša in negativna pa počasi prestavita v levo. Izgleda, da se v tekočini hitro pojavijo mehurčki plina. Zaradi te analogije je bil algoritem poimenovan sortiranje mehurčkov.

Ocena kompleksnosti računanja

Idealni algoritem za razvrščanje mora biti čim hitrejši. Hkrati bi moral odvzeti majhno količino procesorja in pomnilniških virov. In tak postopek, kot je sortiranje mehurčkov, ne more biti najbolj energetsko učinkovit in donosen. Zato ni našel široke uporabe. Če je trenutno manj pomnilnika, potem bi morali procesorski viri skrbeti. Ker digitalni nizi ne smejo biti le veliki, ampak ogromni, bodo stroški računalniških virov nepredvidljivi. Če je sortiranje mehurčkov načeloma hitro obvladovanje naročila v razmeroma majhnem nizu, lahko v velikem primeru pride do zrušitev zaradi prekomerne porabe sredstev. To pomeni, da bo kršeno lastnost univerzalnosti, ki je del algoritma. Poleg tega ima sorta mehurčkov N-kvadratno kompleksnost in je zelo daleč od loga kompleksnosti N. Poleg tega tveganje za neuspeh pri obdelavi velikega niza poveča možnost izgube podatkov zaradi ponovnega zapisovanja celic. Veliko bolj donosno vV tem načrtu bo razvrščanje vstavkov ali Schellov algoritem.

Programska koda

Računalniška koda za jezik C, navedena spodaj v grafičnem dodatku, omogoča razvrščanje mehurčkov. Izdana je kot ločena funkcija tipa void. Ne vrne nobenih vrednosti, vendar uporaba kazalcev spremeni mesta v elementih, odvisno od pogojev razvrščanja. V tem primeru koda rešuje problem razvrščanja mehurčkov celih števil v naraščajočem vrstnem redu.
Za izvajanje te funkcije mora uporabnik ustvariti polje, ki ga je treba izpolniti z zahtevanimi vrednostmi. To lahko storite ročno, tako da na začetku programa določite dimenzijo in število elementov. Hkrati lahko zapolnite polje s konstantnimi vrednostmi. Druga možnost je ustvarjanje univerzalnega programa z razglasitvijo velikega enodimenzionalnega niza 100 elementov.

Razglasitev in inicializacija polja

Z nastavitvijo celoštevilske spremenljivke in podajanjem vrednosti iz tipkovnice lahko omejite število celic, ki bodo zapolnjene. Funkcijo vnosa elementov matrike lahko uporabite tudi s tipkovnice s pomočjo funkcije scanf ("% d", & amp; value). V tem primeru je "% d" spreminjajoči niz, ki pove prevajalniku, da bo po skeniranju pridobljeno celo število. Vrednost spremenljivke bo shranila vrednost, ki je velikost enodimenzionalnega celoštevilskega niza. Če želite uporabiti algoritem za razvrščanje, morate funkciji podati ime polja in njegovo velikost. V situaciji, predstavljeni v grafični aplikaciji, je klic funkcijeRazvrščanje bo izgledalo takole: BubleSort (dataArray, sizeDataArray). Seveda morate na koncu vrstice za funkcijo namesto piko položiti podpičje, kot to zahtevajo pravila sintakse programa. DataArray je torej ime matrike, ki jo želite razvrstiti, in sizeDataArray je njena velikost.
Prenos teh parametrov v funkcijo BubleSort () bo privedel do dejstva, da bodo namesto uporabe sizeArray, kot je prikazano na sliki, operacije v realnem programu izvedene iz sizeDataArray. To pomeni, da bo funkcija BubleSort () uporabila celoštevilsko matriko dataArray. Podobno se prikličejo funkcije printArrayFunction () in ArrayIntegerInputFunction (). Prvi je odgovoren za tiskanje, tj. Za izpisovanje elementov v konzolo. Drugi pa je potreben, da ga zapolnimo z elementi, ki jih je uporabnik vnesel s tipkovnice.
Ta slog programiranja, ko se posamezne operacije izvajajo kot funkcije, močno poveča berljivost kode in pospeši njen razvoj. V takem programu se ločeno vnese polje iz tipkovnice, pri čemer se natisne enaka vrsta mehurčka. Slednje lahko uporabite za urejanje podatkov ali kot sekundarno funkcijo, ki išče najmanjšo in največjo vrednost matrike.

Razvrščanje vstavkov

Razvrščanje po metodi vstavljanja omogoča postopno primerjavo vsakega elementa in konstrukcijo verige, ki je že razvrščena glede na stanje elementov. Posledica vsake nadaljnje primerjave je torej iskanje celice, ki se lahko postavi v novo vrednost. Toda vstavljanje vsakega od njih se opravi že razvrščen del matrike.
Takšna obdelava je hitrejša in ima manj računalniške kompleksnosti. Koda v jeziku C je predstavljena v grafičnem dodatku.
Predstavljen je tudi v obliki funkcije, ki mora kot argument, ki je posredovan imenu, urediti polje in velikost matrike. Tukaj lahko vidite, kako počasno je razvrščanje mehurčkov. Vstavki so podobni delu, ki je bilo opravljeno veliko hitreje in ima kompaktno programsko kodo.

Sorodne publikacije