| Algoritmas | |
| Tipas | Rikiavimo algoritmai |
| Pavadinimas | Įterpimo (Insertion sort) |
| Sudėtingumas | Vidutinis - N²; blogiausias - N² |
| 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, 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; vikipedija, wiki, enciklopedija, knyga, biblioteka, straipsnis, skaityti, nemokamas atsisiuntimas, informacija apie Įterpimo rikiavimo algoritmas, Kas yra Įterpimo rikiavimo algoritmas? Ką reiškia Įterpimo rikiavimo algoritmas?