Lisäyslajittelu
Wikipedia
Lisäyslajittelu (insertion sort) on hidas (O(n2)) ja vakaa lajittelualgoritmi, joka toimii 'paikallaan' (eli ei vaadi lisämuistia). Lisäyslajittelun asymptoottinen suoritusaika on yhtä suuri kuin kuplalajittelulla, mutta käytännössä sen ajoaika on kuitenkin usein huomattavasti tätä pienempi. Yksinkertaisuutensa vuoksi se onkin usein nopein vaihtoehto lajittelualgoritmiksi hyvin pienillä taulukoilla.
Algoritmi toimii pitämällä taulukon alkuosan koko ajan järjestyksessä lisäämällä yksitellen jokaisen alkion käsittelemättömästä loppuosasta oikealle paikalleen alkuosaan.
Ohessa lisäyslajittelun pseudokielinen toteutus:
algoritmi Lisäyslajittelu(taulukko t)
n := taulukon t alkioiden lukumäärä
// Käydään taulukon jokainen (paitsi ensimmäinen) alkio läpi
for i = 2 to n
j := i
// Siirretään alkio oikealle paikalleen järjestettyyn alkuosaan
while(t[j] < t[j-1] ja j > 1)
Vaihda alkioiden t[j] ja t[j-1] arvot keskenään
j := j - 1
end while
end for
