Lisäyslajittelu

Lisäyslajittelu (insertion sort) on hidas (O(n²)) 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;
                }
        }
}