Při práci s informacemi jsou nejziskovějšími způsoby jejího ukládání struktury a matice. Ten může obsahovat jakýkoli druh dat stejného typu, který je vhodný pro práci v programu. Často se používají v internetových obchodech a ve vývoji her. Proto jsou v nich obsažená data opakovaně řazena a měněna na místech a nad nimi jsou prováděna logická nebo matematická operace. Jedním ze způsobů, jak nastavit pořadí v poli, je třídění bublin. Tato publikace bude zkoumat programový kód v jazyce C a logiku permutací.

Algoritmus pro třídění pole

Technická složitost pro programátor nepředstavuje třídění bublinového jednorozměrného pole, ačkoli je zřídka používáno kvůli jeho nízké účinnosti. To je častěji zvažováno ve fázi učení jako nejjednodušší. Nicméně není zdaleka nejúčinnější. Jeho algoritmus se skládá ze sekvenčního porovnání číslic a vzájemného přepisu buněk, pokud je stav pozorován.

Popis třídění krok za krokem

Při první iteraci se postupně porovnávají dvě sousední čísla. Je-li levý větší, pak je přepsán pravým. Minus 8 a 0 podmínky nejsou splněny. A proto se místa nemění. Nula a 5 nejsou také vhodné. 5 a 3 - fit. Nicméně na takové iteraci čtecí rámec nespadá do prvních pět a posune se doprava, protože 5 bylo porovnáno s nulou. To znamená, že se změní další pár míst - 3 a 9. DalšíVšechna nahrazení jsou nabízena čtenáři, aby byla nezávisle přezkoumána bez komentářů autora a studovala algoritmus třídění bublin.


V důsledku všech iterací se pole postupně třídí a to se děje hlavně takto: velké kladné číslice se rychle posunuly napravo, zatímco menší a záporné byly pomalu přemísťovány doleva. Vypadá to, že bubliny plynu v kapalině rychle vyskočí. Kvůli této analogii byl algoritmus pojmenován třídění bublin.

Odhad výpočetní složitosti

Ideální třídící algoritmus by měl být co nejrychlejší. Současně by měl odvézt malé množství procesorových a paměťových prostředků. A takový proces jako třídění bublinek pole nemůže být nejvíce energeticky efektivní a ziskové. Proto nenalezl široké využití. Pokud je momentálně méně paměti, pak by se měly obavy procesorů obávat. Vzhledem k tomu, že digitální pole nemusí být jen velké, ale obrovské, náklady na počítačové zdroje budou nepředvídatelné. V případě, že bubble sort, ve skutečnosti, rychle stoupá vnést řád do pole relativně malý, pak velké selhání může být způsobeno překročení rozpočtu zdrojů. To znamená, že vlastnost univerzálnosti vlastní algoritmu bude porušena. Navíc bublina má složitost N-čtverce a je velmi daleko od logu složitosti N. Kromě toho riziko selhání při zpracování velkého pole zvyšuje pravděpodobnost ztráty dat v důsledku přepisování buněk. Mnohem výhodnější jeV tomto plánu se bude třídit vložky nebo Schellův algoritmus.

Programový kód

Počítačový kód pro jazyk C uvedený níže v grafické příloze umožňuje třídění bublin. Vydává se jako samostatná funkce typu void. Nevrací se žádné hodnoty, ale použití ukazatelů změní místa v prvcích v závislosti na podmínkách třídění. V tomto případě kód řeší problém bubliny třídí pole celých čísel ve vzestupném pořadí.
Pro provedení této funkce musí uživatel vytvořit pole, které musí být vyplněno požadovanými hodnotami. Můžete to provést ručně zadáním rozměru a počtu prvků na začátku programu. Současně můžete vyplnit pole s konstantními hodnotami. Druhou možností je vytvoření univerzálního programu vyhlášením velkého jednorozměrného pole se 100 prvky.

Deklarace a inicializace pole

Nastavení celočíselnou proměnnou a dávat to znamenat, číst přímo z klávesnice, můžete omezit počet buněk, které mají být vyplněny. Můžete také implementovat funkci zadávání prvků pole uživatelem z klávesnice pomocí funkce scanf ("% d", & amp; value). V tomto příkladu je "% d" modifikující řetězec, který řeší kompilátoru, že po skenování bude získána celočíselná hodnota. Proměnná hodnota uloží hodnotu, která je velikost jednorozměrného celočíselného pole. Chcete-li použít třídící algoritmus, musí být název pole a jeho velikost předán funkci. V situaci prezentované v grafické aplikaci volání funkcetřídění bude vypadat takto: BubleSort (dataArray, sizeDataArray). Samozřejmě, že je konec řádku po funkci by měl dát středník namísto bodu, jak je požadováno podle pravidel syntaxe programu. Takže dataArray - je název pole, které chcete třídit a sizeDataArray - je její velikost. Přenos těchto parametrů pro funkce BubleSort (), vedou k tomu, že namísto použití sizeArray, jak je znázorněno na obrázku, Aktuální program operace budou prováděny sizeDataArray. To znamená, že funkce BubleSort () použije celé pole datArray. Podobně, tam je volání funkce printArrayFunction () a ArrayIntegerInputFunction (). První je zodpovědná za tisk, tedy za výstup položky do konzoly. A druhý je zapotřebí pro vyplnění elementy zadanými uživatelem z klávesnice.
Tento styl programování, kde jsou jednotlivé transakce provedena v podobě rysů výrazně zvyšuje čitelnost kódu a urychluje jeho vývoj. V takovém programu předloženého samostatně naplnit pole s klávesnicí, jeho tisku stejné bubble druhu. Ten může být použit k uspořádání dat, nebo jako sekundární funkce navržen tak, aby zde minimální a maximální hmotnost.

Druh vložky

seřadit vložením má alternativní porovnání každého prvku a konstrukce řetězu jsou seřazeny podle stavu položky. Výsledkem každého následného porovnání je hledání buňky, která může být umístěna do nové hodnoty. Ale vložka každého z nich je provedena již tříděná část pole. Takové zpracování je rychlejší a má méně výpočetní složitosti. Kód v jazyce C je uveden v grafické příloze. Je také prezentován ve formě funkce, která jako argumenty předávané jménu potřebuje uspořádat pole a velikost pole. Zde vidíte, jak pomalu je třídění bublin. Vložky jsou podobné práci vykonané mnohem rychleji a mají kompaktní programový kód.