© 2013 All rights reserved.
5

Řadící algoritmy #1

Jedná se o takový algoritmus, který je schopný ze vstupního souboru dat vytvořit jejich posloupnost v předem určených podmínkách. Každý algoritmus se snaží najít takovou posloupnost, pro kterou platí, že předchozí prvek je menší nebo roven a následující prvek je větší nebo roven k aktuálnímu prvku, dle kritérií, které řazení určují.

Pro řazení existuje spousta hotových algoritmů, které se liší v mnoha aspektech, jako je složitost, stabilita, nebo metoda pro řazení.

Od těchto vlastností se odvíjí také požadavky, které jsou na algoritmy kladeny:

  • Minimální paměťové požadavky (paměťová složitost)
  • Rychlost (časová složitost)
  • Délka a srozumitelnost kódu
  • Stabilita
  • Přirozenost

Paměťová náročnost
je mnohdy podceňovaným faktorem a je pravda, že v některých případech není až tak důležitá (od toho se odvíjí výběr správného altoritmu), ale ve většině případů je právě tento požadavek velmi
sorting
důležitý, hlavně při řazení velkého počtu záznamů.

Rychlost altoritmu, nebo její časová složitost, je ovlivňována počtem operací, které je nutno se vstupním souborem provést a je ovlivněna i počtem prvků, které jsou ve vstupním souboru dat. Většinou je tato složitost kvadratická, logaritmická nebo lineární, dle výběru algoritmu.

Délka kódu není až tak důležitý faktor, ale v praxi většinou platí, že čím kratší kód, tím efektivnější zpracování vstupu. Ovšem není to podmínkou.

Stabilita určuje, zda budou seřazené prvky souhlasit s jejích klíči. Většinou jsou při řazení využívány klíče a hodnoty, které se řadí závisle nebo nezávisle na sobě.

Přirozenost je vlastnost, kdy algoritmus je přirozený v případě, že čas řazení již z části seřazené vstupní posloupnosti je menší než čas pro řazení neseřazené posloupnosti.

Podle využívání paměti jsou algoritmy ještě členěny na vnitřní a vnější. Při použití vnitřního algoritmu je nutné, aby byla všechna data načtena a uložena v operační paměti, kam k nim algoritmus přistupuje
Vnější algoritmy se využijí zejména při řazení velkého množství dat, kdy není možné všechna data mít načtená a načítá se jenom část dat, které se postupně řadí.

Bubble sort (bublinkové řazení)

Bubble sort je jeden ze základních algoritmů řazení. Princip spočívá v porovnávání vždy dvou prvků, kdy vstupní soubor dat procházíme od počátku ke konci a dle podmínek řazení vždy tyto dva prvky prohazujeme nebo necháváme netknuté.

Nevýhoda spočívá v tom, že abychom dostali seřazenou posloupnost, je nutné celý vstupní soubor dat projít tolikrát, kolik obsahuje hodnot, od čehož se odvíjí právě velká časová náročnost tohoto algoritmu.

Název Bublinkové řazení (Bubble sort) vznikl právě z principu algoritmu, kdy největší prvky v souboru dat postupně při každém dalším procházení probublávají směrem doprava (dle použitého algoritmu).

Ukázka jednoduchého Bubble sortu v Javě, pro seřazení pole celých čísel, může vypadat takto:

I když je po principiální stránce algoritmus dost pomalý, jde na internetu najít spoustu různých upravených alternativ, které jej vylepšují.

Existuje ještě jedno využití tohoto algoritmu, které je na rozdíl od řazení jedno z nejrychlejších. Jedná se o případ, kdy chceme zjistit, zda je vstupní soubor dat již seřazený nebo nikoli. Pro toto zjištění nám stačí jenom jeden průchod všech vstupních hodnot, při kterém porovnáváme vždy hodnoty dvou, vedle sebe, ležících prvků.

Ukázka takové funkce může v Javě vypadat takto:


Přirozený: Ano
Stabilní: Ano
Minimální časová složitost: O(n)
Průměrná časová složitost: O(n^2)
Maximální časová složitost: O(n^2)

Insertion sort (řazení vkládáním)

Insertion sort je další z algoritmů, který je založen na porovnávání hodnot, podobně jako Bubble sort, ovšem princip je zcela odlišný.

Algoritmus pracuje tak, že prochází neseřazenou strukturu, a každý aktuálně zpracovávaný prvek přesune na jeho konečné místo (některou z konců struktury), kam patří.

Jak vyplívá z podstaty, jeho časová složitost se přímo odvíjí od struktury vstupních dat. Pokud jsou data částečně seřazena, je algoritmus velmi rychlí. Stejně tak je velmi rychlí pro malé obsahy vstupních dat.

Od principu řazení se opět odvíjí název – řazení vkládáním (Insertion sorting), kdy se vstupní prvky struktury přímo vkládají na místo kam patří.

Další výhodou algoritmu je, že dokáže řadit „online“. To znamená, že umožňuje seřadit i předem nenačtenou strukturu, ale hodnoty můžeme do struktury postupně přidávat. Algoritmus nemusí předem znát celkový počet prvků. Takže umožňuje do seřazené struktury velmi jednoduše vložit další prvek a celou strukturu vrátit opět seřazenou.

Ukázkový kód v Javě, pro seřazení pole celých čísel, může vypadat takto:


Přirozený: Ano
Stabilní: Ano
Minimální časová složitost: O(n)
Průměrná časová složitost: O(n^2)
Maximální časová složitost: O(n^2)

Slection sort (řazení výběrem)

Selection sort je principiálně velmi jednoduchý algoritmus. Cílem je postupně procházet celou strukturu vstupních hodnot, ve kterých se hledá vždy nejmenší prvek (nebo největší prvek, dle užití algoritmu), který se posune na konec struktury (nebo na začátek). Tímto postupem se nám postupně zmenšuje počet hodnot, ve kterých je nutné vyhledávat, a na konci (nebo začátku) struktury nám vzniká již seřazená posloupnost.

Nevýhodou je, že i když je na vstupu již částečně seřazená struktura, algoritmus to nerozlišuje a jeho složitost a časová náročnost je pořád stejná, protože se postupně zpracovávají všechny prvky.
Název je opět odvozen od principu, protože algoritmus projde celé pole a vybere v něm jeden, vyhovující, prvek, který zařadí na jedenu z krajních pozic. Při každém průchodu se počet hodnot zmenšuje o jednu (n-1) a tento postup se opakuje, dokud nejsou všechny prvky vyčerpány (n = 0).

Opět jednoduchá ukázka v Javě, pro seřazení pole celých čísel, může vypadat takto:


Přirozený: Ne
Stabilní: Ano
Časová složitost: O(n^2)

Závěrem

Toto jsou tři nejjednodušší řadící algoritmy, se kterými se můžete v praxi setkat. Jejich implementace nemusí být nutně taková, jak je zde uvedeno, a všechny tyto algoritmy je možné libovolně upravit a změnit tak některou jejich vlastnost, většinou na úkor vlastnosti jiné.
V příštím článku se podíváme na další, složitější, řadící algoritmy.

Comments (5)

Selection sort podle tohoto kódu je nestabilni

Článek jsem jen tak proletl, ale na konci mě zarazilo slovní spojení "v praxi setkáte". Ja nevím jak ty, ale já bych se ani s jedním z těchto algoritmů setkal nechtěl, protože by mě to mohlo stát dost času. Tyto algoritmy jsou více méně teoretická věc, která se nepoužívá. Něco jako dvoudobí spalovací motor v autech. Prostě překonáno. Jinak pěkný článek a jen tak dál vzhuru k NP

Zarazilo mě, že píšeš, že Select sort je stabilní, podle mě stabilní neni.

V praxi jde potkat insertion sort jakozto vypln quicsortu pro maly pole (i kdyz i tam byl placnul shell sort)…jinak souhlasim…tohle se v praxi moc nepotka, protoze A) jazyky maji implementovany n*log(n) algoritmy v knihovnach, B) tyhle algoritmy jsou dost pomaly

Ale spis bych se pozastavil nad

"Délka kódu není až tak důležitý faktor, ale v praxi většinou platí, že čím kratší kód, tím efektivnější zpracování vstupu. Ovšem není to podmínkou."

coz je docela nesmysl…takovej heapsort neni zrovna kratkej a je optimalni, takovej bubble sort je kratkej a optimalni neni, radix sort ma 3 radky a slozitost (k*n) :-)

Leave a Reply to Honzajscz Cancel Reply

About
Hi, i am programmer from the Czech Republic. I love web development (Ruby, Ruby on Rails, PHP, Nette) and iOS development (Objective-C, Cocoa).
To cooperate, here is my phone:
+420 608 836