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

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

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).

Toto číslo prohodíme s prvním číslem (zde s 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):

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).

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

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

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