Išrinkimo rikiavimo algoritmas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Algoritmas
Tipas Rikiavimo algoritmai
Pavadinimas Išrinkimo (Selection sort)
Sudėtingumas Vidutinis - N²; blogiausias - N²
Greitos nuorodos
Animacija, vaizduojanti išrinkimo rikiavimo algoritmą

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 | redaguoti vikitekstą]

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

Šaltiniai[redaguoti | redaguoti vikitekstą]

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