Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

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;
      }
    }
  • 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;
      }
    }
    
    
  • Public Sub SelectionSort(cisla() As Integer)
        Dim pomocna As Integer
        Dim minimum As Integer
        For i As Integer = 0 To cisla.Length - 1
            minimum = cisla.Length - 1
            For j As Integer = i To cisla.Length - 1 ' hledání minima
                If cisla(minimum) > cisla(j) Then
                    minimum = j
                End If
            Next
            ' prohození prvků
            pomocna = cisla(minimum)
            cisla(minimum) = cisla(i)
            cisla(i) = pomocna
        Next
    End Sub

V další lekci, Bubblesort, si ukážeme algoritmus Bubblesort i se zdrojovými kódy.


 

Všechny články v sekci
Třídicí/řadicí algoritmy
Přeskočit článek
(nedoporučujeme)
Bubblesort
Článek pro vás napsal David Hartinger
Avatar
Uživatelské hodnocení:
160 hlasů
David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.
Unicorn university David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity