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í.
Pouze tento týden sleva až 80 % na e-learning týkající se Swiftu. Zároveň využij výhodnou slevovou akci až 30 % zdarma při nákupu e-learningu - více informací.
discount 30 + hiring

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
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

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;
      }
    }
    
    

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 Čápka
Avatar
Uživatelské hodnocení:
50 hlasů
David je zakladatelem ITnetwork a programování se profesionálně věnuje 13 let. Má rád Nirvanu, sushi 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

 

 

Komentáře

Avatar
Don
Člen
Avatar
Don:25.9.2011 16:21

Trochu nechápu větu "Nyní cyklem projedeme pole od prvního do posledního prvku (rozsah cyklu je zvýrazněn barevně) a vybereme to nejmenší číslo (zde 9)." Píše se zde že vybereme nejmenší číslo ale v závorce je číslo 9 a v tabulce pracujeme s číslem 1. Myslím že v závorce mělo být napsané číslo 1.

 
Odpovědět
25.9.2011 16:21
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Don
David Čápka:25.9.2011 22:03

V původní verzi článku jsem třídil pomocí hledání maxima, zapomněl jsem to změnit, díky za upozornění :)

Odpovědět
25.9.2011 22:03
One of the most common causes of failure is the habit of quitting when one is overtaken by temporary defeat.
Avatar
martinkobelka
Tvůrce
Avatar
martinkobelka:28.7.2012 13:20

kod pro php

$pole = array(1,8,7,4,2);
for($i=0;$i<count($pole);$i++){
    for($j=$i;$j<count($pole);$j++){
        if($i == $j){
            $min = $pole[$j];
            $cislop = $j;
        }
        else{
            if($pole[$j] < $min){
                $min = $pole[$j];
                $cislop = $j;
            }
        }
    }
    $mezi = $pole[$i];
    $pole[$i] = $min;
    $pole[$cislop] = $mezi;
}

echo implode($pole, ", ");
 
Odpovědět
28.7.2012 13:20
Avatar
jahoda.l
Člen
Avatar
Odpovídá na martinkobelka
jahoda.l:16.4.2013 15:23

Osobně bych to řešil v PHP spíše nějak takto:

function selection_sort(array $sortedArray){
  $lenght = count($sortedArray);
  $temp = null;
  for($actualPossition = 0; $actualPossition < $lenght; ++$actualPossition){
      $min = null;
      for($runPossiton = $actualPossition; $runPossiton < $lenght; ++$runPossiton){
        if($sortedArray[$runPossiton] < $min || $min === null){
          $min = $sortedArray[$runPossiton];
          $temp = $runPossiton;
        }
      }
      $sortedArray[$temp] = $sortedArray[$actualPossition];
      $sortedArray[$actualPossition] = $min;
  }
  return $sortedArray;
}

Dle výkonu je v PHP dobré nepoužívat funkce jako např. "count" při cyklech, jelikož při každém průchodu cyklu se funkce znovu volá. Je tedy výhodnější jí uložit do proměnné.

Další ačkoliv zvláštní performance je používání ++$i namísto $i++ jedná se sice o cca 13% ovšem ale při algorytmu by jsme měli řešit i 13%.

Přikládám ještě odkaz na benchmark: http://www.phpbench.com/

 
Odpovědět
16.4.2013 15:23
Avatar
Michal
Člen
Avatar
Michal:4.5.2014 10:55

C++

template<typename T>
void selectionSort(std::vector<T>& vect)
{
   for (unsigned i = 0, j = 0; i < vect.size() - 1; ++i)
   {
      T min = vect[vect.size() - 1];
      // Hledání minima.
      for (j = i; j < vect.size() - 1; ++j)
         if (vect[j] < min)
            min = vect[j];
      // Prohození.
      std::swap(vect[i], vect[j]);
   }
}
Editováno 4.5.2014 10:57
Odpovědět
4.5.2014 10:55
Don’t worry if it doesn’t work right. If everything did, you’d be out of a job.
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
Maxfx
Tvůrce
Avatar
Maxfx:2.7.2014 20:12
void selectionSort(int f[], int size)
{
        int min = 0;

        for(int i = 0; i < size; i++)
        {
                min = i;

                for(int j = i + 1; j < size; j++)
                {
                        if(f[min] > f[j]) min = j;
                }

                swap(f[i], f[min]);
        }
}
Odpovědět
2.7.2014 20:12
Být ovládán znamená být sledován, pod dohledem, špehován, veden, uzákoněn, reglementován, ohrazen, indoktrinován, pře...
Avatar
Neaktivní uživatel:10.1.2017 17:27

Optimalizovaný kód pre PHP:

function selectionDesc(array $input) {

    $arrayLength = sizeof($input);
    $key = null;

    $i = 0;
    while($i < $arrayLength) {

        $key = $i;
        $min = $input[$i];

        $j = $i + 1;
        while($j < $arrayLength) {

            if($input[$j] > $min) {
                $key = $j;
                $min = $input[$j];
            }

            ++$j;

        }

        $input[$key] = $input[$i];
        $input[$i] = $min;
        ++$i;

    }

    return $input;

}

Pre opačné usporiadanie stačí otočiť porovnávanie v podmienke.

Odpovědět
10.1.2017 17:27
Neaktivní uživatelský účet
Avatar
Rostislav Kuruc
Brigádník
Avatar
Rostislav Kuruc:23.10.2020 10:17

Kod pro Python

def selectionSort(array):
# O(n^2)
    for i in range(len(array)):

        min_index = i
        # prochazime cele pole

        for j in range(i+1, len(array)):
            # projedeme zbyvajici prvky pole (protoze i+1)
            if(array[min_index] > array[j]):
                # nalezli jsme nejmensi prvek, tak si ulozime jeho index
                min_index = j

        # prohodime prvek z prvniho iteracniho cyklu s nejmensim nalezenym
        array[i], array[min_index] = array[min_index], array[i]

    return array
Odpovědět
23.10.2020 10:17
Matematika je programovacim jazykem vesmiru...
Avatar
Odpovídá na Don
Lenka Polláková:28.11.2021 2:53

To je tak no,jednoduchosť sa ťažko chápe. Rozumiem

 
Odpovědět
28.11.2021 2:53
Avatar
Eva Šimerková:8. ledna 10:20

Ahoj, moc jsem nepochopila, jak mám funkci vložit do svého programu.
Učím se programovat v C# a nevím, jestli mám nahradit to "static void Main(string[] args)" tím "public static int[] selectionSort(int[] pole)" a jestli mám to pole určit předtím nebo potom. Bude potom program fungovat? Nebo tam musím zadat ještě něco?

 
Odpovědět
8. ledna 10:20
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 10.