Lekce 1 - Selection sort
Vítejte v kurzu Třídicí/řadicí algoritmy. V tomto on-line kurzu se seznámíme s principy fungování různých třídících algoritmů a vyzkoušíme si jejich implementaci v různých programovacích jazycích.
Požadavky na znalosti
Pro úspěšné zvládnutí kurzu se předpokládají znalosti základní konstrukce daného jazyka dle vašeho výběru. Budou uváděny ukázky kódu v jazycích Python, Csharp, PHP a Java.
Začínáme
Prvním algoritmem bude Selection sort, který je jeden z nejjednodušších a základních algoritmů pro třídění dat.
Selection Sort
Algoritmus Selection sort je často využíván v praxi především pro svou jednoduchost a snadnou implementaci. I když není nejefektivnější v rámci velkých datových množin, je stále užitečný pro malé nebo předem seřazené seznamy.
Princip tohoto algoritmu spočívá v postupném nalezení nejmenšího nebo největšího prvku z nesetříděné části pole a jeho následném přesunu na začátek nebo konec setříděné části pole.
Vlastnosti algoritmu
Selection sort má následující vlastnosti:
| Implementace | Jednoduchá |
|---|---|
| Časová složitost | O(n2) |
| Stabilita | Ne |
| Rychlost | Pomalý |
| Optimalizace pro velký obsah | Ne |
Časovou složitostí rozumíme složitost průměrného případu. Rychlostí pak rychlost vzhledem ke všem třídícím algoritmům.
Příklad
Ukažme si průběh třídění na poli následujících prvků:
| 3 | 5 | 2 | 8 | 9 | 1 |
Průběh třídění pole
Nejprve cyklem projedeme pole od prvního do posledního prvku a vybereme
minimum, kterým je prvek1:
| 3 | 5 | 2 | 8 | 9 | 1 |
Prvek 1 prohodíme s prvním prvkem
3 a získáme první zatříděný prvek:
| 1 | 5 | 2 | 8 | 9 | 3 |
Nyní, od druhého prvku, cyklem opět projedeme pole a
najdeme další minimum, tudíž prvek 2:
| 1 | 5 | 2 | 8 | 9 | 3 |
Prvek opět zatřídíme. Protože již ale máme prvek 1
zatříděný, prvek 2 prohodíme s druhým prvkem
5:
| 1 | 2 | 5 | 8 | 9 | 3 |
Teď máme již dva první prvky správně zatříděné. Tímto způsobem bychom pokračovali dále. Vybírali bychom minimální prvky ze zbylých prvků a třídili je tak dlouho, dokud bychom neměli celé pole 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.
Vizualizace
Podívejme si na vizualizaci třídění:
Video ukázka
Video ukázka třídění vypadá takto:
Zdrojový kód
Nyní pojďme naše znalosti algoritmu implementovat do zdrojového kódu:
-
public static void selectionSort(int[] list) { int temp, min; for (int i = 0; i < (list.length - 1); i++) { min = list.length - 1; // hledání minima for (int j = i; j < (list.length - 1); j++) if (list[min] > list[j]) min = j; // prohození 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; // hledání minima for (int j = i; j < (list.Length - 1); j++) if (list[min] > list[j]) min = j; // prohození 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; // hledání minima for ($j = $i; $j < (count($list) - 1); $j++) if ($list[$min] > $list[$j]) $min = $j; // prohození 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.
David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.