Įterpimo rikiavimo algoritmas
Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
| Algoritmas | |
| Tipas | Rikiavimo algoritmai |
| Pavadinimas | Įterpimo (Insertion sort) |
| Sudėtingumas | Vidutinis - N2; blogiausias - N2 |
| 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, sarašu, bet ne masyvu).
[taisyti] Pavyzdžiai
Pavyzdys Pascal kalba:
procedure Įterpimas;
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;
[taisyti] Nuorodos
- Rikiavimo algoritmų sudėtingumas
- Įterpimo metodas vaizdžiai
- Įterpimo metodas vaizdžiai
- Įterpimo metodas vaizdžiai
Daugiau apie Įterpimo metodą aplankykite Įterpimo metodas

