Įterpimo rikiavimo algoritmas

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

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

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

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;

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