Bublové triedenie jednorozmerného poľa: algoritmus, programový kód v jazyku C.

Pri práci s informáciami najvýhodnejšiespôsoby ich ukladania sú štruktúry a súbory. Ten môže obsahovať ľubovoľné údaje jedného typu, ktoré je vhodné použiť v programe. Často sa používajú v práci on-line obchodov a pri vývoji hier. Preto sa dáta, ktoré sa v nich nachádzajú, opakovane triedia a vymieňajú a na nich sa vykonávajú logické alebo matematické operácie. Jedným zo spôsobov, ako priviesť poradie do poľa, je triedenie bublín. Táto publikácia bude študovať svoj C kód a logiku permutácií.

Algoritmus triedenia poľa

Technické ťažkosti pre programátorabublinové triedenie jednorozmerného poľa nereprezentuje, aj keď sa používa pomerne zriedkavo kvôli jeho nízkej účinnosti. V štádiu výcviku sa častejšie považuje za najjednoduchšiu. Zďaleka to však nie je najefektívnejšie. Jeho algoritmus pozostáva zo striedania porovnávania číslic a navzájom prepísaných buniek, ak je splnená podmienka.

Popis triedenia krok za krokom

Na prvej iterácii dvesusedných čísel. Ak je ľavica väčšia, potom je prepisovaná na miestach s pravým. Mínus 8 a 0 podmienky nespĺňajú. Preto sa nemenia na miestach. Nula a 5 tiež nezapadajú. 5 a 3 sú vhodné. Pri tejto iterácii však čítací rámec neklesne na prvých piatich, ale posúva doprava, pretože od 5 sa porovnával s nulou. Znamená to, že nasledujúci pár - 3 a 9 zmení miesta a potom sa čitateľovi ponúkne, aby preskúmal všetky substitúcie nezávisle od autorových komentárov a aby preskúmal algoritmus triedenia bublín.

V dôsledku všetkých iteračných postupov je pole postupneje zoradený a to je v podstate: veľké kladné čísla sa pohybujú rýchlo doprava, zatiaľ čo menšie a negatívne sú pomaly posunuté doľava. Vyzerá to, že bubliny plynu v kvapaline rýchlo vystúpia. Kvôli tejto analógii bol algoritmus nazývaný triedením bublín.

Odhad výpočtovej zložitosti

Ideálny algoritmus triedenia by mal byťčo najrýchlejšie. Súčasne by malo zaberať malé množstvo zdrojov CPU a pamäte. A takýto proces ako triedenie bublín poľa nemôže byť energeticky najefektívnejší a najvýhodnejší. Z dôvodu širokej aplikácie nenašiel. Ak je v súčasnosti s pamäťou menej problémov, potom by mali byť zdroje procesora znepokojené. Keďže digitálne polia nemusia byť len veľké, ale obrovské, spotreba počítačových zdrojov bude nepredvídateľná.

Ak je triedenie bublín v zásade rýchlesa vyrovnáva s usporiadaním poriadku v relatívne malom poli, potom vo veľkom môže dôjsť k poruchám spôsobeným nadmerným výdavkom zdrojov. To znamená, že vlastnosť univerzality vlastná algoritmu bude porušená. Triedenie bublom má N-štvorcový zložitosť a je veľmi vzdialené od logaritmu N zložitosti. Riziko zlyhania pri spracovaní veľkého poľa navyše zvyšuje pravdepodobnosť straty dát v dôsledku prepisovania buniek. V tomto ohľade bude oveľa výhodnejšie vkladanie triedy alebo algoritmus Shell.

Kód softvéru

Nasledujúce je v grafickej aplikáciipočítačový kód pre jazyk C umožňuje vykonať triedenie bublín. Vyjadruje sa ako samostatná funkcia typu void. Nevrátia žiadne hodnoty, ale pomocou ukazovateľov sa prvky vymieňajú v závislosti od podmienok triedenia. V tomto prípade kód rieši problém triedenia bublín z množstva celých čísel vo vzostupnom poradí.

Ak chcete vykonať túto funkciu, používateľ musívytvorte pole, ktoré je potrebné vyplniť požadovanými hodnotami. To je možné vykonať ručne nastavením dimenzie a počtu prvkov na začiatku programu. Potom môžete vyplniť pole s konštantnými hodnotami. Druhou možnosťou je vytvoriť univerzálny program vyhlásením veľkého jednorozmerného poľa 100 prvkov.

Vyhlásenie a inicializácia poľa

Priradenie celočíselnej premennej a jej priradenieHodnota načítaná z klávesnice môže 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", & hodnota). V tomto príklade je "% d" modifikačný reťazec, ktorý informuje kompilátor, že po skenovaní bude prijatá celočíselná hodnota. Hodnota premennej uloží hodnotu, ktorá je veľkosťou jednorozmerného celočíselného poľa.

Ak chcete použiť triedenie algoritmus, mali by stepremeniť funkciu na názov poľa a jeho veľkosť. V situácii prezentovanej v grafickej aplikácii bude výzva na funkciu triedenia vyzerať takto: BubleSort (dataArray, sizeDataArray). Samozrejme, na konci riadku po funkcii by ste mali namiesto periódy umiestniť bodkočiarku, ako to vyžadujú pravidlá syntaxe programu. Takže, dataArray je názov poľa, ktoré chcete zoradiť, a sizeDataArray je jeho veľkosť.

Odovzdávanie týchto parametrov do funkcie BubleSort ()bude to mať za následok, že namiesto použitia sizeArray, ako vidíte na obrázku, v skutočnom programe budú operácie vykonané s veľkosťouDataArray. To tiež znamená, že funkcia BubleSort () použije celé číslo dataArray. Podobne sa volá funkcia printArrayFunction () a ArrayIntegerInputFunction (). Prvý je zodpovedný za tlač, tj za výstup do konzoly prvkov. A druhá je potrebná na to, aby sa naplnila prvkami zadanými používateľom z klávesnice.

Tento štýl programovania, keď je izolovanýoperácie sa vykonávajú vo forme funkcií, výrazne zvyšujú čitateľnosť kódu a urýchľujú jeho vývoj. V takomto programe sa pole vyplní oddelene od klávesnice, vytlačí sa a bublina sa zoraďuje. Tá môže byť použitá na usporiadanie údajov alebo ako sekundárna funkcia určená na nájdenie minima a maxima poľa.

Inserčné triedenie

Pri triedení metódou vloženiastriedavo porovnávať každý prvok a zostrojiť reťazec položiek, ktoré už boli zoradené podľa daného stavu. V dôsledku toho je výsledkom každého následného porovnania vyhľadávanie bunky, do ktorej môže byť umiestnená nová hodnota. Vloženie každého z nich sa však uskutočňuje v už usporiadanej časti poľa.

Takéto spracovanie je rýchlejšie a má menej výpočtovej zložitosti. Kód C je uvedený v grafickej aplikácii.

Tiež sa uvádza v podobe funkcie, v ktorej jeAko argumenty sa prenáša názov poľa, ktoré sa má objednať, a veľkosť poľa. Tu môžete vidieť, ako spomaliť triedenie bublín. Vložené podobné práce je oveľa rýchlejší a má kompaktný kód.