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
1.
function selectionSort(array a)
2.
for
i in
0
-> a.length -
2
do
3.
maxIndex = i
4.
for
j in (i +
1
) -> (a.length -
1
)
do
5.
if
a[j] > a[maxIndex]
6.
maxIndex = j
7.
prohoď(a[i], a[maxIndex])
01.
/**
02.
* Razeni vyberem (od nejvyssiho)
03.
* @param array pole k serazeni
04.
*/
05.
public
static
void
selectionSort(
int
[] array) {
06.
for
(
int
i =
0
; i < array.length -
1
; i++) {
07.
int
maxIndex = i;
08.
for
(
int
j = i +
1
; j < array.length; j++) {
09.
if
(array[j] > array[maxIndex]) maxIndex = j;
10.
}
11.
int
tmp = array[i];
12.
array[i] = array[maxIndex];
13.
array[maxIndex] = tmp;
14.
}
15.
}
01.
/**
02.
* Razeni vyberem (od nejvyssiho)
03.
* @param array pole k serazeni
04.
* @param size velikost pole
05.
*/
06.
void
selectionSort(
int
array[],
int
size) {
07.
for
(
int
i = 0; i < size - 1; i++) {
08.
int
maxIndex = i;
09.
for
(
int
j = i + 1; j < size; j++) {
10.
if
(array[j] > array[maxIndex]) maxIndex = j;
11.
}
12.
int
tmp = array[i];
13.
array[i] = array[maxIndex];
14.
array[maxIndex] = tmp;
15.
}
16.
}
01.
/**
02.
* Razeni vyberem (od nejvyssiho)
03.
* @param array pole k serazeni
04.
*/
05.
public
static
void
SelectionSort(
int
[] array)
06.
{
07.
for
(
int
i = 0; i < array.Length - 1; i++)
08.
{
09.
int
maxIndex = i;
10.
for
(
int
j = i + 1; j < array.Length; j++)
11.
{
12.
if
(array[j] > array[maxIndex]) maxIndex = j;
13.
}
14.
int
tmp = array[i];
15.
array[i] = array[maxIndex];
16.
array[maxIndex] = tmp;
17.
}
18.
}
01.
procedure
SelectSort(
var
X : ArrayType; N :
integer
);
02.
var
03.
I,
04.
J,
05.
K,
06.
Y :
integer
;
07.
begin
08.
for
I :=
1
to
N -
1
do
09.
begin
10.
K := I;
11.
Y := X[I];
12.
for
J := (I +
1
)
to
N
do
13.
if
(X[J] < Y)
then
14.
begin
15.
K := J;
16.
Y := X[J]
17.
end
;
18.
X[K] := X[J];
19.
X[I] := Y;
20.
end
21.
end
;