Įterpimo rikiavimo algoritmas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Algoritmas
Tipas Rikiavimo algoritmai
Pavadinimas Įterpimo (Insertion sort)
Sudėtingumas Vidutinis - N2; blogiausias - N2
Greitos nuorodos

Įterpimo algoritmas (angl. insertion sort) - vienas iš paprastų, bet nelabai efektyvių rikiavimo algoritmų. Algoritmo privalumai - paprasta suprogramuoti, efektyvus mažiems duomenų kiekiams ar beveik surikiuotiems duomenims, naudoja mažai atminties. Algoritmas yra stabilus. Pagrindinis principas - imamas kiekvienas elementas iš eilės ir įterpiamas į jam skirtą vietą jau surikiuotoje duomenų grupėje.

Įterpimo algoritmas laukiamu atveju naudoja apytikriai N²/4 lyginimų ir N²/8 keitimų vietomis, blogiausiu atveju - dvigubai daugiau operacijų. Veikia geriau su tam tikrom duomenų struktūrom (pavyzdžiui, sarašu, bet ne masyvu).

[taisyti] Pavyzdžiai

Pavyzdys Pascal kalba:

procedure Įterpimas;
var i,j,v:integer;
begin
  for i:=2 to N do
  begin
    v:=a[i]; j:=i;
    while a[j-1]>v do
      begin
        a[j]:=a[j-1];
        j:=j-1
      end;
    a[j]:=v
  end
end;

[taisyti] Nuorodos

Daugiau apie Įterpimo metodą aplankykite Įterpimo metodas