Įterpimo rikiavimo algoritmas

Į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.

Algoritmas
Tipas	Rikiavimo algoritmai
Pavadinimas	Įterpimo (Insertion sort)
Sudėtingumas	Vidutinis - N²; blogiausias - N²
Greitos nuorodos	Algoritmai Rikiavimo algoritmai Įterpimo Šablonas

Animacija, vaizduojanti įterpimo rikiavimo algoritmą

Į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, sąrašu, bet ne masyvu).

Kai žaidėjai rankiniu būdu rūšiuoja kortas bridžo žaidime, dauguma naudoja rikiavimo metodą, panašų įterpimo algoritmą.^[1]

Pavyzdžiai

Pavyzdys Pascal kalba:

procedure Iterpimas (var a:array of integer; N:integer);
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;

Šaltiniai

1. Sedgewick, Robert (1983). Algorithms. Addison-Wesley. p. 95. ISBN 978-0-201-06672-2.

Nuorodos

• Rikiavimo algoritmų sudėtingumas
• Įterpimo metodas vaizdžiai
• Įterpimo metodas vaizdžiai Archyvuota kopija 2005-09-27 iš Wayback Machine projekto.
• Įterpimo metodas vaizdžiai