11. Základní algoritmy a datové struktury pro vyhledávání a řazení. Vyhledávací stromy, rozptylovací tabulky. Prohledávání grafu. Úlohy dynamického programování. Asymptotická složitost a její určování.
Základní algoritmy a datové struktury pro vyhledávání a řazení
Základní algoritmy řazení
V popiscích jednotlivých algoritmů se vyskytují následující hesla a charakteristiky:
Rozděl a panuj
Tato metoda označuje ty algoritmy pro práci s daty, které řeší problém rozdělením řešené úlohy na dílčí části(podproblémy), nad kterými se provádí algoritmická operace. Často se tato metoda implementuje rekurzivně nebo iterativně a původní úloha se dělí na stále menší části.
Stabilní/nestabilní algoritmus
Stabilním algoritmus je ten, který zachovává pořadí stejných prvků, tak jak byly na vstupu v seznamu. Seřadí je na odpovídající místo, ale v rámci stejných prvků zůstanou ve stejném pořadí. U nestabilního algoritmu toto nezaručíme.
Mergesort je stabilní řadicí algoritmus typu rozděl a panuj s asymptotickou složitostí Ο ( n* log ( n ) ) . Merge sort pracuje na bázi slévání již seřazených částí pole.
Merge
Proces merge nebo-li slévání probíhá následovně. Máme dva seznamy, u kterých víme, že jsou seřazeny ve stejném pořadí. Postupně je procházíme a díváme se, který z právě iterovaných členů je větší(případně menší, záleží, jak srovnávám). Ten větší(resp. menší) z dvojice vložíme do pomocného seznamu. Takto se dostanem do fáze, kdy jeden ze seznamů, kterými iterujem, je už prázdný. Můžeme tedy zbytek druhého vzít a celý ho zkopírovat na konec do pomocného seznamu.
Ve vypsaném kódu je první while cyklus na řádku 13 porovnávání. Z následujících dvou cyklů(21 a 25) se provede jen jeden a to ten, který zkopíruje do pomocného seznamu zbývající členy jednoho ze dvou iterovaných seznamů.
/**
* Slevani pro Merge sort
* @param array pole k serazeni
* @param aux pomocne pole (stejne velikosti jako razene
* @param left prvni index, na ktery smim sahnout
* @param right posledni index, na ktery smim sahnout
*/
privatestaticvoidmerge(int[] array, int[] aux, int left, int right){
Základní algoritmy a datové struktury pro vyhledávání a řazení
Základní algoritmy řazení
Mergesort
/** * Slevani pro Merge sort * @param array pole k serazeni * @param aux pomocne pole (stejne velikosti jako razene * @param left prvni index, na ktery smim sahnout * @param right posledni index, na ktery smim sahnout */private static void merge(int[] array, int[] aux, int left, int right) { int middleIndex = (left + right)/2; int leftIndex = left; int rightIndex = middleIndex + 1; int auxIndex = left; while(leftIndex <= middleIndex && rightIndex <= right) { if (array[leftIndex] >= array[rightIndex]) { aux[auxIndex] = array[leftIndex++]; } else { aux[auxIndex] = array[rightIndex++]; } auxIndex++; } while (leftIndex <= middleIndex) { aux[auxIndex] = array[leftIndex++]; auxIndex++; } while (rightIndex <= right) { aux[auxIndex] = array[rightIndex++]; auxIndex++; }}