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(n²)
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ů:

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:

Prvek 1 prohodíme s prvním prvkem 3 a získáme první zatříděný prvek:

Nyní, od druhého prvku, cyklem opět projedeme pole a najdeme další minimum, tudíž prvek 2:

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:

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ě:

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.

Článek pro vás napsal David Hartinger

Uživatelské hodnocení:

166 hlasů

David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.

David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.

Aktivity