Pri práci s informáciami sú najziskovejšími spôsobmi ich ukladania štruktúry a súbory. Ten môže obsahovať akýkoľvek druh údajov rovnakého typu, ktorý je vhodný na použitie v práci programu. Často sa používajú v internetových obchodoch a pri vývoji hier. Preto sa dáta, ktoré sa v nich nachádzajú, opakovane triedia a menia na miestach a nad nimi sa vykonávajú logické alebo matematické operácie. Jeden spôsob, ako nastaviť poradie v poli, je triedenie bublín. Táto publikácia preskúma programový kód v jazyku C a logiku permutácií.

Algoritmus triedenia poľa

Technická zložitosť pre programátora nepredstavuje rozdelenie jedno- rozmerného poľa bublinami, aj keď sa zriedkavo používa kvôli jeho nízkej efektívnosti. To je častejšie považované vo fáze učenia za najjednoduchšie. Zďaleka to však nie je najúčinnejšie. Jeho algoritmus pozostáva z postupného porovnávania číslic a recipročného prepísania buniek, ak je stav pozorovaný.

Popis triedenia krok za krokom

Pri prvej iterácii sa postupne porovnávajú dve susedné čísla. Ak je ľavý väčší, je prepísaný pravým. Mínus 8 a 0 podmienky nie sú splnené. A preto sa miesta nemenia. Nulová a 5 sú tiež nevhodné. 5 a 3 - zapadajú. Avšak na takejto iterácii čítací rámec nespadá do prvej päťky a posúva doprava, pretože 5 bolo porovnané s nulou. Znamená to zmenu nasledujúceho páru miest - 3 a 9. ĎalejVšetky čítania sú ponúkané čitateľovi, aby boli nezávisle preskúmané bez komentárov autora a aby študovali algoritmus triedenia bublín.


V dôsledku všetkých iterácií sa pole postupne triedi a to prebieha najmä nasledovne: veľké kladné čísla sa rýchlo posunuli napravo, zatiaľ čo menšie a negatívne sa pomaly preskupovali doľava. Vyzerá to, že rýchlo sa objavia bublinky v kvapaline. Kvôli tejto analógii bol algoritmus označený ako triedenie bublín.

Odhad výpočtovej zložitosti

Ideálny algoritmus triedenia by mal byť čo najrýchlejšie. Zároveň by mal odobrať malé množstvo zdrojov procesora a pamäte. A takýto proces, akým je bublina triediť pole, nemôže byť energeticky najefektívnejšia a najvýhodnejšia. Preto nebol široký. Ak je v súčasnosti menej pamäte, potom by sa mali zdroje procesora obávať. Keďže digitálne polia nemusia byť len veľké, ale obrovské, náklady na počítačové zdroje budú nepredvídateľné. Ak sa triedenie bublín v zásade rýchlo vyrovná s objednávaním objednávky v pomerne malom poli, potom vo veľkom môže dôjsť k nehodám v dôsledku nadmerného využitia zdrojov. To znamená, že vlastnosť univerzálnosti vlastnej algoritmu bude porušená. Navyše, druh bubliny má N-štvorcový zložitosť a je veľmi ďaleko od logu zložitosti N. Riziko zlyhania pri spracovaní veľkého poľa navyše zvyšuje pravdepodobnosť straty údajov v dôsledku prepísania buniek. Oveľa viac ziskovéV tomto pláne sa bude triediť vkladanie alebo Schellov algoritmus.

Programový kód

Počítačový kód pre jazyk C uvedený nižšie v grafickej prílohe umožňuje triedenie bublín. Vydáva sa ako samostatná funkcia typu void. Nevráti žiadne hodnoty, ale použitie ukazovateľov mení miesta v prvkoch v závislosti od podmienok triedenia. V tomto prípade kód rieši problém bublina triedenie poľa celých čísel vo vzostupnom poradí.
Ak chcete vykonať túto funkciu, používateľ musí vytvoriť pole, ktoré je potrebné vyplniť požadovanými hodnotami. Môžete to urobiť manuálne zadaním dimenzie a počtu prvkov na začiatku programu. Súčasne môžete vyplniť pole s konštantnými hodnotami. Druhou možnosťou je vytvorenie univerzálneho programu tým, že deklarujeme veľké jednorozmerné pole 100 prvkov.

Vyhlásenie a inicializácia poľa

Nastavením celočíselnej premennej a jej zadaním hodnoty z klávesnice môžete obmedziť počet buniek, ktoré budú vyplnené. Môžete tiež implementovať funkciu zadávania prvkov poľa používateľom z klávesnice pomocou funkcie scanf ("% d", & amp; hodnota). V tomto príklade je "% d" modifikačný reťazec, ktorý informuje kompilátor, že po skenovaní získa celočíselnú hodnotu. Hodnota premennej uloží hodnotu, ktorá je veľkosťou jednorozmerného celočíselného poľa. Ak chcete použiť algoritmus triedenia, musí byť meno poľa a jeho veľkosť prenesené na funkciu. V situácii prezentovanej v grafickej aplikácii volanie funkcieTriedenie bude vyzerať takto: BubleSort (dataArray, sizeDataArray). Samozrejme, na konci riadku po funkcii by ste mali umiestniť bodkočiarku namiesto bodky, ako to vyžadujú pravidlá syntaxe programu. Takže, dataArray je názov poľa, ktoré chcete zoradiť, a sizeDataArray je jeho veľkosť. Prenos týchto parametrov do funkcie BubleSort () bude mať za následok skutočnosť, že namiesto použitia sizeArray, ako je vidieť na obrázku, budú operácie v reálnom programe vykonané z sizeDataArray. To znamená, že funkcia BubleSort () bude používať celé pole dátového_array. Podobne sa volajú funkcie printArrayFunction () a ArrayIntegerInputFunction (). Prvý z nich je zodpovedný za tlač, tj za výstupy do konzoly. A druhá je potrebná na vyplnenie s prvkami zadanými používateľom z klávesnice.
Tento programovací štýl, keď sa jednotlivé operácie vykonávajú ako funkcie, výrazne zvyšuje čitateľnosť kódu a urýchľuje jeho vývoj. V takomto programe je pole oddelené od klávesnice a jeho vytlačovanie je rovnaké. Tá môže byť použitá na usporiadanie údajov alebo ako sekundárna funkcia, ktorá sa snaží nájsť minimálne a maximálne pole.

Triedenie vložiek

Triedenie podľa spôsobu vkladania umožňuje postupné porovnanie každého prvku a konštrukciu reťaze už roztriedeného podľa podmienok prvkov. V dôsledku toho je výsledkom každého následného porovnania vyhľadávanie bunky, ktorá môže byť umiestnená do novej hodnoty. Ale vložka každého z nich je vykonaná už zoradená časť poľa. Takéto spracovanie je rýchlejšie a má menej výpočtovej zložitosti. Kód v jazyku C je uvedený v grafickej prílohe. Je tiež prezentovaný vo forme funkcie, ktorá ako argumenty prenesené na meno potrebuje usporiadať pole a veľkosť poľa. Tu môžete vidieť, ako pomalé je triedenie bublín. Vložky sú podobné práci, ktorá sa vykonáva oveľa rýchlejšie a má kompaktný programový kód.