Co je třídění polí?

Třídění polí je proces převzetí jednotlivých prvků pole a jejich uspořádání v nějakém typu logického pořadí podle řady pravidel definovaných uživatelem. Proces zahrnuje procházení maticí, jeden prvek najednou, a testování tohoto prvku proti okolním prvkům, aby se určilo, zda je třeba přesunout do jiného indexu v rámci pole. Při třídění polí existuje několik algoritmů, které lze použít, zejména pokud jsou podmínky třídění číselné, na rozdíl od něčeho více svévolného. Většina algoritmů třídění polí se měří podle rychlosti a účinnosti, přičemž nejpomalejší algoritmy jsou nejjednodušší programování a nejrychlejší je mnohem složitější.

Nejjednodušší algoritmus třídění polí se nazývá bublinové řazení a také nejpomalejší. Proces začíná smyčkou, která bude procházet každým prvkem v poli. Aktuální prvek je porovnán s dalším prvkem v poli a pokud je další prvek nižší, než aktuální prvek, jsou data v indexech přepnuta. Nevýhodou třídění bublin je to, že musí několikrát procházet maticí, aby vytvořily všechny potřebné swapy pro třídění polí. V nejzákladnějších implementacích bude řazení procházet celé pole jednou úplnou dobou pro každý prvek, který obsahuje.

Výběrové řazení používá algoritmus, který provádí třídění polí o něco efektivněji než třídění bublin, ale stále vyžaduje více iterací skrz pole. Toto řazení začíná opakováním pole, aby se našel prvek s nejnižší hodnotou. Tento prvek se poté umístí do prvního indexu pole a zvýší se některé sledovací proměnné. Cyklus se pak opakuje a nyní hledá další nejnižší hodnotu, která se pak umístí do druhého indexu pole. Proces pokračuje, dokud prvek nejvyšší hodnoty není umístěn v posledním indexu pole.

Metoda třídění polí, která může být efektivní, ale někdy komplikovaná implementace, se nazývá quicksort. Quicksorting zahrnuje převzetí hodnoty, která je uprostřed všech možných hodnot držených v poli. Algoritmus prochází všemi prvky pole a na konec pole umístí všechny hodnoty větší než střední číslo a na začátek nižší hodnoty. Tento proces se provádí rekurzivně na blocích pole, dokud na konci není celé pole seřazeno. Za předpokladu, že střední hodnota použitá pro pole je poměrně přesná, může to být velmi rychlý způsob řazení.

Jedním z faktorů, který může ovlivnit algoritmus třídění polí, jsou prostředky, pomocí kterých jsou data testována na ekvivalenci. Jednoduchá čísla lze snadno porovnat, pro které hodnoty jsou vyšší, ale nemusí tomu tak být u složitých tříd dat, ve kterých je třeba porovnat více podmínek. Čím déle trvá porovnání toho, zda je jeden prvek větší nebo menší než druhý, tím déle bude trvat, než algoritmus roztřídí pole.