Selection sort je jedným z najjednoduchších radiacich algoritmov. Jeho
myšlienka spočíva v nájdení minima, ktoré sa presunie na začiatok poľa
(alebo môžeme hľadať aj maximum a to dávať na koniec). V prvom kroku teda
nájdeme najmenší prvok v poli a ten potom presunieme na začiatok. V druhom
kroku už nebudeme pri hľadaní minima brať do úvahy skôr nájdenej minimum.
Po dostatočnom počte krokov dostaneme pole zoradené. Algoritmus má
nepríliš výhodnú časovú zložitosť a nie je stabilný. Je však veľmi
jednoduchý na pochopenie aj implementáciu.
Vlastnosti algoritmu
časová zložitosť
(n 2)
stabilita
nie
rýchlosť
pomalý
Pozn. je myslená časová zložitosť priemerného prípadu a rýchlosť
vzhľadom ku všetkým triediacim algoritmom.
Priebeh
Máme pole nasledujúcich prvkov:
3
5
2
8
9
1
Teraz cyklom prejdeme poľa od prvého do posledného prvku (rozsah cyklu je
zvýraznený farebne) a vyberieme to najmenšie číslo (tu 1).
3
5
2
8
9
1
Toto číslo prehodíme s prvým číslom (tu s 3):
1
5
2
8
9
3
Týmto krokom sme dostali prvý prvok v poľa klasifikované. Teraz cyklom
opäť prejdeme poľa a nájdeme najmenší prvok. Ale pretože ten úplne
najmenší už máme na začiatku, nebudeme ho zahŕňať a prejdeme teda pole
od druhého do posledného prvku a opäť vyberieme najmenší prvok (2):
1
5
2
8
9
3
Prvok si opäť zatriedime, pretože už máme 1 prvok klasifikované z minula,
prehodíme ho s druhým prvkom (5).
1
2
5
8
9
3
Teraz máme už 2 prvej prvky správne. Takto budeme pokračovať ďalej,
budeme vyberať minimum zo zvyšných prvkov a zatřizovat ho tak dlho, kým
nebudeme mať pole celej zotriedené. Ďalšie kroky algoritmu by vyzerali
nasledovne:
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ý prvok je už logicky klasifikované, preto si môžeme tento krok
ušetriť. A je hotovo.
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;
}
}
// 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 minimafor j:=i to (length(list) - 1) doif (list[min] > list[j]) then
min:=j;
// prohozeni prvku
temp:=list[min];
list[min]:=list[i];
list[i]:=temp;
end;
end;
# vraci setridene poledef 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
David sa informačné technológie naučil na Unicorn University - prestížnej súkromnej vysokej škole IT a ekonómie.