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 Šablonas

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.

Algoritmas priklauso „brutalios jėgos“ algoritmams,^[1] 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

redaguoti

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 C++ 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;  } }

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

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

[1]