Išrinkimo rikiavimo algoritmas

Algoritmas
Tipas	Rikiavimo algoritmai
Pavadinimas	Išrinkimo (Selection sort)
Sudėtingumas	Vidutinis - N²; blogiausias - N²
Greitos nuorodos	Algoritmai Rikiavimo algoritmai Išrinkimo

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.

Animacija, vaizduojanti išrinkimo rikiavimo algoritmą

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

1. Amaratunga, Kevin. „Sorting“. web.mit.edu. Nuoroda tikrinta 2024-02-03.