Lekce 1 - Selection sort
Selection sort je jedním z nejjednodušších řadících algoritmů. Jeho myšlenka spočívá v nalezení minima, které se přesune na začátek pole (nebo můžeme hledat i maximum a to dávat na konec). V prvním kroku tedy nalezneme nejmenší prvek v poli a ten poté přesuneme na začátek. V druhém kroku již nebudeme při hledání minima brát v potaz dříve nalezené minimum. Po dostatečném počtu kroků dostaneme pole seřazené. Algoritmus má nepříliš výhodnou časovou složitost a není stabilní. Je však velice jednoduchý na pochopení i implementaci.
Vlastnosti algoritmu
Časová složitost | (n2) |
---|---|
Stabilita | Ne |
Rychlost | Pomalý |
Pozn. je myšlena časová složitost průměrného případu a rychlost vzhledem ke všem třídícím algoritmům.
Průběh
Máme pole následujících prvků:
3 | 5 | 2 | 8 | 9 | 1 |
Nyní cyklem projedeme pole od prvního do posledního prvku (rozsah cyklu je zvýrazněn barevně) a vybereme to nejmenší číslo (zde 1).
3 | 5 | 2 | 8 | 9 | 1 |
Toto číslo prohodíme s prvním číslem (zde s 3):
1 | 5 | 2 | 8 | 9 | 3 |
Tímto krokem jsme dostali první prvek v pole zatříděný. Nyní cyklem opět projedeme pole a najdeme nejmenší prvek. Ale protože ten úplně nejmenší již máme na začátku, nebudeme ho zahrnovat a projedeme tedy pole od druhého do posledního prvku a opět vybereme nejmenší prvek (2):
1 | 5 | 2 | 8 | 9 | 3 |
Prvek si opět zatřídíme, protože již máme 1 prvek zatříděný z minula, prohodíme ho s druhým prvkem (5).
1 | 2 | 5 | 8 | 9 | 3 |
Teď máme již 2 první prvky správně. Takto budeme pokračovat dále, budeme vybírat minimum ze zbylých prvků a zatřizovat ho tak dlouho, dokud nebudeme mít pole celé setříděné. Další kroky algoritmu by vypadaly následovně:
1 | 2 | 5 | 8 | 9 | 3 |
1 | 2 | 3 | 8 | 9 | 5 |
1 | 2 | 3 | 8 | 9 | 5 |
1 | 2 | 3 | 5 | 9 | 8 |
1 | 2 | 3 | 5 | 9 | 8 |
1 | 2 | 3 | 5 | 8 | 9 |
Poslední prvek je již logicky zatříděný, proto si můžeme tento krok ušetřit. A je hotovo.
Vizualizace
Video ukázka
Zdrojový kód
-
public static void selectionSort(int[] list) { int temp, min; for (int i = 0; i < (list.length - 1); i++) { min = list.length - 1; // hledani minima for (int j = i; j < (list.length - 1); j++) if (list[min] > list[j]) min = j; // prohozeni prvku temp = list[min]; list[min] = list[i]; list[i] = temp; } }
-
public static void selectionSort(int[] list) { int temp, min; for (int i = 0; i < (list.Length - 1); i++) { min = list.Length - 1; // hledani minima for (int j = i; j < (list.Length - 1); j++) if (list[min] > list[j]) min = j; // prohozeni prvku temp = list[min]; list[min] = list[i]; list[i] = temp; } }
-
{PHP} function selection_sort(array &$list) { for ($i = 0; $i < (count($list) - 1); $i++) { $min = count($list) - 1; // hledani minima for ($j = $i; $j < (count($list) - 1); $j++) if ($list[$min] > $list[$j]) $min = $j; // prohozeni prvku $temp = $list[$min]; $list[$min] = $list[$i]; $list[$i] = $temp; } } $list = [3, 5, 2, 8, 9, 1]; selection_sort($list); print_r($list); {/PHP}
V další lekci, Bubblesort, si ukážeme algoritmus Bubblesort i se zdrojovými kódy.
Komentáře


Zobrazeno 10 zpráv z 10.