Swift týden
Pouze tento týden sleva až 80 % na e-learning týkající se Swift
30 % bodů zdarma na online výuku díky naší Slevové akci!

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;
      }
    }
  • // setridi vlozene pole, predpoklada indexovani od 0
    procedure selection_sort(var list: array of integer);
    var i, j, min, temp: integer;
    begin
      for i:=0 to (length(list) - 2) do begin
        min:=length(list) - 1;
        // hledani minima
        for j:=i to (length(list) - 1) do
          if (list[min] > list[j]) then
            min:=j;
        // prohozeni prvku
        temp:=list[min];
        list[min]:=list[i];
        list[i]:=temp;
      end;
    end;
  • # vraci setridene pole
    def selection_sort(list)
      (list.length - 1).times do |i|
        min = list.length - 1
        # hledani minima
        i.upto(list.length - 1) do |j|
          min = j if (list[min] > list[j])
        end
        # prohozeni prvku
        temp = list[min]
        list[min] = list[i]
        list[i] = temp
      end
    end

 

Všechny články v sekci
Třídící/řadící algoritmy
Článek pro vás napsal David Čápka
Avatar
Jak se ti líbí článek?
19 hlasů
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn university Autor sítě se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity (6)

 

 

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
Jsem moc rád, že jsi na síti, a přeji ti top IT kariéru, ať jako zaměstnanec nebo podnikatel. Máš na to! :)
Avatar
martinkobelka
Redaktor
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
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
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.
Avatar
Maxfx
Redaktor
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
Samuel Illo
Redaktor
Avatar
Samuel Illo :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
www.samuelillo.com | www.github.com/lamka02sk
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 7 zpráv z 7.