Triedenie je najcastejsou operaciou nad datami.Triedi sa podla nejakeho kluca.V pripade ze data je napriklad kartoteka zamestnancov mozme pouzit ako kluc vek zamestnanca a dostaneme utriedeny zoznam podla veku. Samotne triednie sa deli na vonkajsie a vnutorne.Vonkajsie triedenie sa pouziva na triedenie velkych datovych oblasti ktore sa nezmestia do pamete napr subor.Vnutorne triedenie sa pouziva na triedenie poli ktore sa nachadzaju v pameti. Techniky triedenia medzi vonkajsim a vnutornim triedenim su rozdielne a vyplivaju zo samotnej moznosti pracovat s datami. My sa budeme venovat vnutorenmu triedeniu.
vnutorne triedenie sa deli na:
priame metody a logaritmicke.
Priame metody:
-priame vkladanie
-priamy vyber
-priama vymena (alebo tiez bublinove triedenie)
Logaritmicke:
-shellovo triedenie
-triedenie haldou
-quicksort
Priame metody su charakteristicke tym ze su jednoduche,vyzaduju radovo n^2 porovnani klucov a su efektivne pre male polia.
Logaritmicke metody su charakteristicke tym ze su zlozitejsie,vyzaduju n.log n porovani klucov a su rychlejsie ako priame metody.
Definicie priamych metod:
Priame vkladanie - triedit sa zacina od druheho prvku pola.Prvok x najde svoj ciel tak ze ho porovnavame s jeho susedom a ak je sused vacsi tak ho posunieme vpravo.Triedenie sa konci ked:
1) sused je mensi ako x
2) dosiahneme na dolny index pola
Samotne priame vkladanie ma este svoje rozsirenie v podobe binarneho vkladania. Toto vylepsenie sa tyka rychlejsieho najdenia miesta na ulozenie prvku. Ale vzhladom na to ze nie je az tak efektivny ako by sa dalo na prvy pohlad zdat, nebudeme sa nim zaoberat.Je to opak binarne vyhladavania takze kto ma zaujem -> bsearch(3).
Priamy vyber - triedime od zaciatku pola.Prechadzame po poli a snazime sa najst najmensi prvok pola.Ked ho najdeme vymenime ho s prvkom na nasej aktualnej pozicii.Triedenie sa konci ked dosiahneme na horny index pola Tento typ triedenia patri medzi najefektivnejsie priame metody.
Priame vkladanie - triedi sa od zaciatku. Jeho hlavnou vlastnostou je vymena prvkov.Ked si predstavime ze pole lezi vertikalne a prirovname prvky k bublinkam,tak kazdy prvok ako keby vybublal na svoje miesto v poli :). Preto sa aj vola bublinove triedenie.
Cize zhruba ako to vyzera v C: for (i = 0; i < MAXLEN; i++) for (r = MAXLEN - 1; r >= i; r--) if (pole[r - 1] > pole[r]) swap(&pole[r - 1], &pole[r]);Tento typ triedenia ma svoje rozsirenie v podobe Shakersort-u. Namiesto slov vam radsej ponuknem tento zdrojak: while (left <= right) { for (down = right; down >= left; down--) if (pole[down - 1] > pole[down]) { swap(&pole[down - 1], &pole[down]); i = down; } left = i + 1; for (up = left; up < right + 1; up++) if (pole[up - 1] > pole[up]) { swap(&pole[up - 1], &pole[up]); i = up; } right = i - 1; } Kde left je dolny index pola,right je horny index pola a funkcia swap vymeni hodnoty na indexoch.v92
