Bubble třídění jednorozměrného pole: algoritmus, programový kód v jazyce C

Při práci s informacemi jsou nejvýhodnějšími způsoby, jak je uložit, struktury a matice. Ten může obsahovat jakákoliv data jednoho typu, která je vhodná pro použití v programu. Často se používají v práci internetových obchodů a při vývoji her. Data, která jsou v nich obsažena, se proto opakovaně třídí a vyměňují a na nich se provádějí logické nebo matematické operace. Jeden způsob, jak přinést pořadí do pole, je třídění bublin. Tato publikace bude studovat svůj C kód a logiku permutací.

Algoritmus řazení algoritmů

Technické obtíže pro programátora bubble druhu není jednorozměrné pole, ale používá jen zřídka vzhledem k nízké účinnosti. To je častěji zvažováno ve fázi výcviku jako nejjednodušší. Nicméně není zdaleka nejúčinnější. Jeho algoritmus se skládá ze střídavého porovnání číslic a vzájemně přepsaných buněk, pokud je splněna podmínka.

Podrobný popis třídění

Při první iteraci se postupně porovnávají dvě sousední čísla. Je-li levý větší, pak je přepsán na místech s pravým. Minus 8 a 0 podmínky nesplňují. Proto se na místech nemění. Zero a 5 se také nehodí. 5 a 3 jsou vhodné. Při této iteraci však čtecí rámec nespadá na pět nejlepších, ale posune se doprava, protože od počátku 5 se porovnával s nulou. To znamená, že další pár - 3 a 9 změní místa. Pak je čtenář nabídnut ke kontrole všech substitucí nezávisle bez komentářů autora a ke studiu algoritmu třídění bublin.

V důsledku všech iterací postupně seřazené pole, a to se vyskytuje hlavně takto: velká kladná čísla se rychle přesunout na pravé straně, zatímco menší a záporný směrem doleva pomalu předělaný. Vypadá to, jako kdyby plyn bubliny v kapalině rychle vyskočí. Vzhledem k této analogie a algoritmu to bylo voláno bubble sort.

Odhad výpočetní složitosti

Ideální třídící algoritmus by měl být co nejrychlejší. Současně by mělo zabrat malé množství zdrojů procesoru a paměti. A takový proces, jako je třídění bublinek pole, nemůže být energeticky nejúčinnější a výnosnější. Kvůli široké aplikaci nenašel. Pokud je s pamětí v současné době méně problémů, pak by měly být zdroje procesoru znepokojeny. Vzhledem k tomu, že digitální pole mohou být nejen velké, ale obrovské, spotřeba počítačových zdrojů bude nepředvídatelná.

Pokud se třídění bublin v zásadě rychle vyrovná s uspořádáním pořadí v poměrně malém poli, pak v rozsáhlém případě může dojít k poruchám způsobeným nadměrným výdajem zdrojů. To znamená, že vlastnost univerzality vlastněná algoritmu bude porušena. Navíc, třídění bublin má složitost N-čtverce a je velmi daleko od logaritmu složitosti N. Navíc riziko selhání při zpracování velkého pole zvyšuje pravděpodobnost ztráty dat v důsledku přepsání buněk. V tomto ohledu bude mnohem výhodnější třídění vkládání nebo algoritmus Shell.

Kód softwaru

Počítačový kód pro jazyk C v grafické aplikaci umožňuje provádět třídění bublin. Vyjadřuje se jako samostatná funkce typu void. Nevrací žádné hodnoty, ale pomocí ukazatelů swapy prvků závisí na podmínkách řazení. V tomto případě kód řeší problém třídění bublin pořadí celých čísel ve vzestupném pořadí.

K provedení této funkce musí uživatel vytvořit pole, které musí být vyplněno požadovanými hodnotami. To lze provést ručně nastavením rozměru a počtu prvků na začátku programu. Pak můžete pole vyplnit s konstantními hodnotami. Druhou možností je vytvořit univerzální program vyhlášením velkého jednorozměrného pole se 100 prvky.

Vyhlášení a inicializace pole

Zadáním celočíselné proměnné a přiřazením hodnoty čtené z klávesnice můžete omezit počet buněk, které budou vyplněny. Můžete také implementovat funkci zadávání prvků pole uživatelem z klávesnice pomocí funkce scanf ("% d", " hodnota). V tomto příkladu je "% d" modifikační řetězec, který říká kompilátoru, že po skenování bude přijat celočíselná hodnota. Hodnota proměnné uloží hodnotu, která představuje velikost jednorozměrného celočíselného pole.

Chcete-li použít třídící algoritmus, musíte předat název pole a jeho velikost funkce. V situaci zobrazené v grafické aplikaci bude volání funkce řazení vypadat takto: BubleSort (dataArray, sizeDataArray). Samozřejmě, že na konci řádku po funkci byste měli místo středového bodu namísto období, jak to vyžadují pravidla pro syntaxi programu. Takže dataArray je název pole, které chcete třídit, a sizeDataArray je jeho velikost.

Přenos těchto parametrů ve funkci BubleSort () povede k tomu, že namísto použití SizeArray, jak je vidět na obrázku, ve skutečném provozu programu se bude provádět s sizeDataArray. To také znamená, že v BubleSort () funkce celé číslo pole dataArray budou použity. Stejně tak je zde volání funkce printArrayFunction () a ArrayIntegerInputFunction (). Prvním z nich je zodpovědný za tisk, to znamená odnětí prvků v konzole. Druhý je nutná pro jeho plnicích prvků se přivedou z klávesnice uživatelem.

Tento styl programování, když jsou izolované operace vykresleny ve formě funkcí, výrazně zvyšuje čitelnost kódu a urychluje jeho vývoj. V takovém programu je pole vyplněno odděleně od klávesnice, vytištěno a bublina seřídí sama. Ten může být použit pro uspořádání dat nebo jako sekundární funkce určená k nalezení minimálního a maximálního pole.

Vložení třídění

Při třídění vložením se předpokládá, že každý prvek je porovnán postupně a je sestaven řetězec položek, které jsou již řazeny podle daného stavu. Výsledkem každého následného porovnání je hledání buňky, do které může být umístěna nová hodnota. Vložení každého z nich se však provádí v již tříděné části pole.

Takové zpracování je rychlejší a má méně výpočetní složitosti. Kód C je zobrazen v grafické aplikaci.

Je také vykreslen jako funkce, ve které je název pořadí, které má být uspořádáno, a velikost pole jsou předány jako argumenty. Zde vidíte, jak zpomaluje třídění bublin. Vložené podobné práce je mnohem rychlejší a má kompaktní kód.