Įterpimo rikiavimo algoritmas

Įterpimo algoritmas () – 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, 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ą.

 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 

 Nuorodos 
 Rikiavimo algoritmų sudėtingumas
 Įterpimo metodas vaizdžiai
 Įterpimo metodas vaizdžiai 
 Įterpimo metodas vaizdžiai

Kategorija:Rikiavimo algoritmai

no:Sorteringsalgoritme#Innstikksortering