Jaké třídicí algoritmy by měl znát junior Java Developer?
Pojďme si rozebrat 5 klíčových algoritmů
Vývojáři v Javě nepíší jednoduché třídicí algoritmy sami, ale používají hotová řešení a metody kolekcí. Algoritmické úlohy jsou však při pohovorech na juniorské pozice navrhovány, proto si dnes vysvětlíme, jaké typy třídění musíte znát, abyste práci dostali.
Jak se měří výkonnost algoritmů
Třídění je algoritmus a efektivita každého algoritmu se měří pomocí velkého zápisu "O".
"O" odpovídá za počet jednoduchých operací, které musí algoritmus provést, a může měřit čas nebo spotřebovanou paměť. Například kolik operací je potřeba k seřazení pole čísel nebo k nalezení nejmenší hodnoty. Tento přístup pomáhá odhadnout, jak se bude doba provádění algoritmu zvyšovat s rostoucím počtem vstupních dat - metodě lze předat pole 10 nebo 1000 čísel.
Pro každý algoritmus lze odhadnout nejhorší, průměrný a nejlepší případ.
Například nejhorší případ nastane, když jsou prvky v poli zcela promíchané. Pro absolvování pohovoru si stačí zapamatovat nejhorší a průměrný odhad času.
Úkol může znít:
"Napište metodu, která seřadí čísla v nesetříděném poli vzestupně. Pak uveďte časovou náročnost algoritmu."
Existuje více než 25 třídicích algoritmů, ale na příkladu řešení této úlohy popíšeme 5 klíčových, přičemž budeme postupovat od jednoduchých ke složitějším a efektivnějším.
Takto se liší složitost algoritmů:
- O(n) - lineární složitost znamená, že každý prvek pole bude třeba zkontrolovat 1krát.
- O(n log n) - počet kontrol bude roven logaritmu počtu prvků pole.
- O(n^2) - počet kontrol bude roven n^2, kde n je počet prvků.
1. Bublinkové třídění
Nejjednodušším a zároveň nejhorším řešením je bublinkové třídění. Dokud není pole setříděno (isSorted = false), procházíme ve smyčce všechny prvky a porovnáváme aktuální a následující (array[i] >array[i+1]) hodnoty. Pokud je aktuální prvek větší než následující, prohodíme je. temp přiřadíme k array[i], pak array[i] přiřadíme k array[i+1] a array[i+1] přirovnáme k temp. Metoda prochází celé pole, dokud se nejmenší hodnoty nenacházejí na začátku pole.
Čím větší je vstupní pole, tím více průchodů nad ním je třeba provést, což znamená, že čas na porovnání prvků se zvýší.
public void bubbleSort(int[] array) {
boolean isSorted = false;
int temp;
while(!isSorted) {
isSorted = true;
for (int i = 0; i < array.length-1; i++) {
if (array[i] > array[i + 1]) {
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
isSorted = false;
}
}
}
}
V nejhorším a průměrném případě má toto třídění nejvyšší časovou náročnost ze všech metod - kvadratickou O(n^2).
2. Třídění podle výběru
Provedeme ho tak, že projdeme celé pole a najdeme v něm nejmenší prvek, který pak přesuneme na výchozí pozici. Tím se počáteční pozice pro další průchod posune doprava.
public static void selectionSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int position = i;
int min = array[i];
for (int j = i + 1; j < array.length; j++) {
if (array[j] < min) {
position = j;
min = array[j];
}
}
array[position] = array[i];
array[i] = min;
}
}
Toto řazení je považováno za nestabilní, pokud je aplikováno na složitější datové struktury. Pokud řadíte pole objektů, tento algoritmus změní pořadí objektů se stejným klíčem, ale různými hodnotami. Nejhorší a střední odhad času bude O(n^2).
3. Třídění podle insertů
Pro řazení podle insertů musíme prvky posunout doprava, dokud nejsou mezi nejbližšími nejvyššími a nejnižšími hodnotami (řádky 5-9).
public void insertSort(int[] array) {
for (int left = 0; left < array.length; left++) {
int key = array[left];
int i = left - 1;
for (; i >= 0; i--) {
if (key < array[i]) {
array[i + 1] = array[i];
} else {
break;
}
}
array[i + 1] = key;
}
}
Na rozdíl od předchozí metody toto třídění nemění pořadí stejných prvků a je stabilní. Složitost pro nejhorší a průměrný případ je O(n^2), ale v nejlepším případě je O(n) díky tomu, že nemusíme procházet pole podruhé.
4. Náhodné třídění
Smysl tohoto třídění spočívá v tom, že procházíme pole nejen na konec (řádky 8-12), ale také na začátek (řádky 21-26). V obou blocích kódu v podstatě používáme bublinkové třídění.
void cocktailSort(int[] array) {
boolean isSwapped = true;
int start = 0;
int end = array.length;
while (isSwapped == true) {
isSwapped = false;
for (int i = start; i < end - 1; ++i) {
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
isSwapped = true;
}
}
if (isSwapped == false)
break;
isSwapped = false;
end = end - 1;
for (int i = end - 1; i >= start; i--) {
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
isSwapped = true;
}
}
start = start + 1;
}
}
Časový odhad v nejhorším i nejlepším případě bude také O(n^2), ale v nejlepším případě bude lineární O(n).
5. Rychlé třídění
Nejefektivnějším způsobem je rychlé třídění. Nejprve vybereme jeden prvek a pak vůči němu seřadíme všechny ostatní.
public void quickSort(int[] array, int low, int high) {
if (low >= high) return;
int pivot = array[low + (high - low) / 2];
int i = low, j = high;
while (i <= j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (low < j) quickSort(array, low, j);
if (high > i) quickSort(array, i, high);
}
Na řádku 3 označíme prvek uprostřed pole jako odkaz. Poté rozdělíme pole na dvě části (řádky 5-12). Všechny prvky s menšími hodnotami přesuneme před referenční prvek, s většími hodnotami (řádky 14-20). Pomocí rekurze aplikujeme metodu na levé a pravé hodnoty (řádky 22-23). Pokud již není co třídit, metoda se ukončí na druhém řádku. Nejhorší případ je stále O(n^2), ale průměr je mnohem lepší - O(n log n).
K pochopení struktury metod třídy Arrays, kolekcí a rozhraní Stream API potřebujete znát algoritmy třídění. Algoritmy s různými "O" nejlépe demonstrují, jak se odhaduje složitost metod. Pokud pochopíte rozdíl mezi kvadratickou a lineární složitostí, můžete přestat psát zbytečné smyčky a budete vědět, kde získat hotovou implementaci.
Autor: Bidenko Dmitrij
