Įterpimo algortimas Spausdinti
( 4 Votes )

Parašė Aurimas Šimkus   

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

 

Pavyzdys C++ kalba:

void Iterpimas(int mas[], int n)
{
 int i, j, tmp;
 for (i = 1; i < n; i++)
 {
 j = i;
 while (j > 0 && mas[j - 1] > mas[j])
 {
 tmp = mas[j];
 mas[j] = mas[j - 1];
 mas[j - 1] = tmp;
 j--;
 }
 }
}