Insertion sort

Insertion sort is een sorteer-algoritme.

Het begint door de eerste twee elementen uit de set te sorteren. Als deze op hun plaats staan, voegen we het derde element op de juiste plaats toe. Dit doen we totdat we alle elementen op hun plaats hebben gezet.

Dit is eigenlijk de manier waarop een speler zijn kaarten schikt bij een kaartspel. Vandaar dat deze routine ook de Cardsort genoemd wordt.

Een voorbeeld in C van insertion sort. Twee functies maken het voorbeeld eenvoudiger. Om een array met integers te sorteren met insertion sort moet je de functie insertionsort aanroepen met als 1ste argument de array en als 2de argument het aantal integers in die array. De functie zoek_en_plaats wordt aangeroepen door insertionsort en zet een integer op de juiste plaats in een gesorteerde array.

void zoek_en_plaats(int gegeven,int array[],int lengte){
 //lengte is het aantal gesorteerde, de echte lengte van array moet 1 groter zijn
 int i,j;

 for(i=0;i<lengte;i++){ //zoek de juiste plaats voor het gegeven
  if(gegeven<array[i]){ //dit is de juiste plaats
   for(j=lengte;j>i;j--) array[j]=array[j-1]; //zet alles na het gegeven 1 plaats verder
   array[i]=gegeven; //zet het gegeven juist
   return; //stop zoeken
  }
 }
 array[lengte]=gegeven; //dit is het grootste gegeven dus zet het achteraan
}

void insertionsort(int data[],int lengte){
 int resultaat[lengte];
 int i;

 resultaat[0]=data[0]; //zet het eerste gegeven vooraan
 for(i=1;i<lengte;i++) zoek_en_plaats(data[i],resultaat,i); //zet de andere gegevens juist
 for(i=0;i<lengte;i++) data[i]=resultaat[i]; //zet resultaat in data
}