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
publicstaticvoid selectionSort(int[] list) {
int temp, min;
for (int i = 0; i < (list.length - 1); i++) {
min = list.length - 1;
// hledani minimafor (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;
}
}
publicstaticvoid selectionSort(int[] list) {
int temp, min;
for (int i = 0; i < (list.Length - 1); i++) {
min = list.Length - 1;
// hledani minimafor (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;
}
}