Lisäyslajittelu

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

Esimerkkitoteutus C-kielellä

void    insertionsort(void *tab, int ts, int vs, int (*cmp)(void *a, void *b))
{
        int             i;
        int             j;
        char    *ctab;

        if (tab != NULL && ts > 1 && vs > 0)
        {
                i = 0;
                ctab = (char *)tab;
                while (++i < ts)
                {
                        j = i + 1;
                        while (--j > 0 && (*cmp)(ctab + (j - 1) * vs, ctab + j * vs) > 0)
                                swap(ctab + (j - 1) * vs, ctab + j * vs, vs);
                }
        }
}

void    swap(void *a, void *b, int vs)
{
        char    c;
        int             i;

        if (a != b)
        {
                i = -1;
                while (++i < vs)
                {
                        c = *((char *)a + i);
                        *((char *)a + i) = *((char *)b + i);
                        *((char *)b + i) = c;
                }
        }
}

Luokka:Lajittelualgoritmit

no:Sorteringsalgoritme#Innstikksortering