Selection sort

Algoritmy Třídění 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

Autorem widgetu s vizualizací je Jenkings

Video ukázka

Účinkují: Anatoliy Kybkalo

Kamera: Martin Balák

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

 

  Aktivity (1)

Článek pro vás napsal David Čápka
Avatar
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 College Autor se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.

Jak se ti líbí článek?
Celkem (9 hlasů) :
4.777784.777784.777784.777784.77778


 


Miniatura
Všechny články v sekci
Třídící/řadící algoritmy
Miniatura
Následující článek
Bubblesort

 

 

Komentáře

Avatar
Don
Člen
Avatar
Don:

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:

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
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
martinkobelka
Redaktor
Avatar
martinkobelka:

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:

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:

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:
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...
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 6 zpráv z 6.