AlgoritmasTipas Rikiavimo algoritmaiPavadinimas Įterpimo Insertion sort Sudėtingumas Vidutinis N blogiausias N Greitos n

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

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

Šaltiniai

Sedgewick, Robert (1983). Algorithms. Addison-Wesley. p. 95. ISBN .

Nuorodos

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

[1] Sedgewick, Robert (1983). Algorithms. Addison-Wesley. p. 95. ISBN .