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ä

#include <stdio.h>
#include <stdlib.h>

void swap(void *valkio1, void *valkio2, int koko) /* kahden alkion paikkojen vaihtoa varten */
{
  if(koko > 0)
    {
      char *apu;
      if((apu=(char *)malloc(koko))!=NULL)
        {
          int i1=0;
          for(i1=0; i1<koko; i1++)
            *(apu+i1)=*((char *)valkio2+i1);
          for(i1=0; i1<koko; i1++)
            *((char *)valkio2+i1)=*((char *)valkio1+i1);
          for(i1=0; i1<koko; i1++)
            *((char *)valkio1+i1)=*(apu+i1);
          free(apu);
          apu=NULL;
        }
    }
}

void insertionsort(void *alkio, int lkm, int koko, int (*cmp)(void *valkio1, void *valkio2))
{
  if(alkio != NULL && lkm > 1 && koko > 0) /* jonkinlaiset järkevät alkuehdot */
    {
      int i1=0, i2=0;
      for(i1=1; i1<lkm; i1++)
        {
          i2=i1;
          while(i2>0 && cmp((char *)alkio+i2*koko, (char *)alkio+(i2-1)*koko)>0)
            {
              swap((char *)alkio+i2*koko, (char *)alkio+(i2-1)*koko, koko);
              i2--;
            }
        }
    }
}