Selection sort (řazení výběrem) je jednoduchý nestabilní řadící algoritmus se složitostí . V porovnání s dalšími kvadratickými algoritmy je selection sort v obecném případě rychlejší než bubble sort, avšak pomalejší než insertion sort. Výhodou selection sortu oproti algoritmům s asymptotickou složitostí
(quicksort, merge sort, heapsort) je jeho konstantní paměťová složitost.
Princip
Selection sort vychází z myšlenky, že pokud řadíme pole od největšího prvku k nejmenšímu, tak první bude nejvyšší prvek, za ním nejvyšší prvek ze zbytku pole atd., čili stačí pouze postupně vybírat nejvyšší prvky z neseřazené části pole a umísťovat je na konec seřazené části.
Příklad
(3 2 8 7 6) // zadání pole, řaďmě od největšího k nejmenšímu
(3 2 8 7 6) // nejvyšší číslo je 8, prohoďme ho tedy s číslem 3 na indexu 0
(8 2 3 7 6) // nejvyšší číslo je 7, prohoďme ho tedy s číslem 2 na indexu 1
(8 7 3 2 6) // nejvyšší číslo je 6, prohoďme ho tedy s číslem 3 na indexu 2
(8 7 6 2 3) // nejvyšší číslo je 3, prohoďme ho tedy s číslem 2 na indexu 3
(8 7 6 3 2) // seřazeno
(3 2 8 7 6) // nejvyšší číslo je 8, prohoďme ho tedy s číslem 3 na indexu 0
(8 2 3 7 6) // nejvyšší číslo je 7, prohoďme ho tedy s číslem 2 na indexu 1
(8 7 3 2 6) // nejvyšší číslo je 6, prohoďme ho tedy s číslem 3 na indexu 2
(8 7 6 2 3) // nejvyšší číslo je 3, prohoďme ho tedy s číslem 2 na indexu 3
(8 7 6 3 2) // seřazeno
Vizualizace
Kód
function selectionSort(array a)
for i in 0 -> a.length - 2 do
maxIndex = i
for j in (i + 1) -> (a.length - 1) do
if a[j] > a[maxIndex]
maxIndex = j
prohoď(a[i], a[maxIndex])
/**
* Razeni vyberem (od nejvyssiho)
* @param array pole k serazeni
*/
public static void selectionSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int maxIndex = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] > array[maxIndex]) maxIndex = j;
}
int tmp = array[i];
array[i] = array[maxIndex];
array[maxIndex] = tmp;
}
}
/**
* Razeni vyberem (od nejvyssiho)
* @param array pole k serazeni
* @param size velikost pole
*/
void selectionSort(int array[], int size) {
for (int i = 0; i < size - 1; i++) {
int maxIndex = i;
for (int j = i + 1; j < size; j++) {
if (array[j] > array[maxIndex]) maxIndex = j;
}
int tmp = array[i];
array[i] = array[maxIndex];
array[maxIndex] = tmp;
}
}
/**
* Razeni vyberem (od nejvyssiho)
* @param array pole k serazeni
*/
public static void SelectionSort(int[] array)
{
for (int i = 0; i < array.Length - 1; i++)
{
int maxIndex = i;
for (int j = i + 1; j < array.Length; j++)
{
if (array[j] > array[maxIndex]) maxIndex = j;
}
int tmp = array[i];
array[i] = array[maxIndex];
array[maxIndex] = tmp;
}
}
procedure SelectSort(var X : ArrayType; N : integer);
var
I,
J,
K,
Y : integer;
begin
for I := 1 to N - 1 do
begin
K := I;
Y := X[I];
for J := (I + 1) to N do
if (X[J] < Y) then
begin
K := J;
Y := X[J]
end;
X[K] := X[J];
X[I] := Y;
end
end;