Algoritmas | |
Tipas | Rikiavimo algoritmai |
Pavadinimas | Išrinkimo (Selection sort) |
Sudėtingumas | Vidutinis - N²; blogiausias - N² |
Greitos nuorodos |
Išrinkimo algoritmas (angl. selection sort) – vienas iš paprasčiausių rikiavimo algoritmų. Pagrindinis principas – minimalų elementą reikia rašyti į pirmą duomenų sekos vietą, tada taikyti tą patį principą posekiui be pirmojo elemento ir t. t.
![image](https://www.wiki-data.lt-lt.nina.az/image/aHR0cHM6Ly93d3cud2lraS1kYXRhLmx0LWx0Lm5pbmEuYXovaW1hZ2UvYUhSMGNITTZMeTkxY0d4dllXUXVkMmxyYVcxbFpHbGhMbTl5Wnk5M2FXdHBjR1ZrYVdFdlkyOXRiVzl1Y3k4NUx6azBMMU5sYkdWamRHbHZiaTFUYjNKMExVRnVhVzFoZEdsdmJpNW5hV1k9LmdpZg==.gif)
Algoritmas priklauso „brutalios jėgos“ algoritmams, bet dažnai naudojamas labai ilgiems įrašams su trumpais laukais rikiuoti. Algoritmo vykdymo metu kiekvienas iš elementų bus perkeltas į kitą vietą ne daugiau kaip vieną kartą.
Algoritmas naudoja apie N²/2 lyginimų ir N keitimų, taigi sudėtingumas yra O(N²).
Pavyzdys
Pavyzdys Pascal kalba:
procedure Išrinkimas (var a:array of integer; N:integer); var i, j, nuo, t: integer; begin for i := 1 to N-1 do begin nuo := i; for j :=i+1 to N do if a[j] < a[nuo] then nuo := j; t := a[nuo]; a[nuo] := a[i]; a[i] := t end; end;
Pavyzdys kalba:
void Išrinkimas { int nuo, t; for(int i = 0; i < N - 1; i++) { nuo = i; for(int j = i+1; j < N; j++) { if (a[j] < a[nuo]) nuo = j; } t = a[nuo]; a[nuo] = a[i]; a[i] = t; } }
Šaltiniai
- Amaratunga, Kevin. „Sorting“. web.mit.edu. Nuoroda tikrinta 2024-02-03.