Často budeme chtít vyhledat ve velkém množství dat údáj, který nás zajímá - telefonní číslo své přítelkyně (svého přítele) apod. Vyhledávat data můžeme v zásadě dvojím způsobem a to:
Lineární vyhledávání je oproti binárnímu časově náročnější (představte si, že byste v telefonním seznamu hledali od prvního záznamu), ale na druhou stranu není potřeba data nijak třídit. Častěji však budeme chtít mít data setříděná a to nejen pro potřeby vyhledávání. Zase je několik způsobů jak lze data utřídit.
Na příkladu, ve kterém budeme chtít utřídit vzestupně pět čísel, si vysvětlíme tři základní způsoby třídění. Pro lepší pochopení jsou metody i znázorněny.
5 7 1 3 4 5 7 1 3 4 1|7 5 3 4 1 3|5 7 4 1 3 4|7 5 1 3 4 5 7 |
Metoda SELECT SORTPracuje tak, že vyhledá ve skupině prvků minimum (podtrženo) nebo maximum podle toho, jestli chceme třídit vzestupně nebo sestupně, a umístí jej na první místo ve skupině. Proces se opakuje, přičemž velikost tříděného úseku se zmenšuje (odděleno svislou čárou). |
5 7 1 3 4 5 7 1 3 4 5 7 1 3 4 5 1 7 3 4 5 1 3 7 4 5 1 3 4 7 1 5 3 4 7 1 3 5 4 7 1 3 4 5 7 1 3 4 5 7 |
Metoda BUBLE SORTAneb bublinkové třídění. Jednotlivé prvky při něm doslova probublávají tak, že výsledkem je balík setříděných dat (na příkladu si povšiměte probublávání 5 a 7). Principem BUBLE SORTu je porovnávání sousedních prvků (podtrženo) a jejich případné prohození podle toho, jak chceme data třídit (vzestupně/sestupně). Probublávání se musí většinou několikrát opakovat a končí tehdy, když při průchodu celou množinou nedošlo k výměně. |
5 7 1 3 4 5|7 1 3 4 5 7|1 3 4 1 5 7|3 4 1 3 5 7|4 1 3 4 5 7 |
Metoda INSERT SORTTéž nazývána metodou přímého zakládání. Data se rozdělí (svislá čára) na "setříděnou" a nesetříděnou část a pak se jednotlivé prvky z nesetříděné části zakládají na příslušné místo do setříděné části. Tato metoda je nejsložitější na algoritmizaci. Složitost vyplývá z posunu více prvků najednou při zakládání do "setříděné" části (jak je vidět na příkladu). |
Samozřejmě existují i složitější, avšak efektivnější metody jako QUICK SORT. Jejich výkladu se tu však věnovat nebudeme.
Cvičení: Cvičení 21 Cvičení 22