Insertion sort

Insertion sort is een sorteeralgoritme.

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.

De tijdscomplexiteit is O(n²) in de meeste gevallen en in het beste geval, als de waarden al bijna gesorteerd zijn, is de tijdscomplexiteit O(n).

Een voorbeeld in C++ van insertion sort.

template <typename T>
void insertion_sort(vector<T> &v){
	for(int i=1; i<v.size(); i++){
		// de i eerste elementen staan reeds in volgorde
		T hulp = v[i]; // we halen het i-de element er uit.
		int j=i-1;
		while(j>=0 && hulp<v[j]){
			// alle elementen groter dan het i-de element worden 1 plaats naar rechts opgeschoven
			v[j+1] = v[j];
			j--;
		}
		v[j+1] = hulp; // we voegen het uitgehaalde in op zijn juiste plaats.
	}
}

Een alternatieve implementatie:

for (auto i = start; i != end; ++i)
    std::rotate(std::upper_bound(start, i, *i), i, std::next(i));

Een voorbeeld in Csharp van insertion sort.

Je doorloopt de hele tabel, per te controleren getal(1):
1) Houd je de inhoud bij van dit getal(1)
2) zolang dat er een getal links(2) van het te sorteren getal(1) staat, controleer je als deze(1) kleiner is
3) indien Ja, dan verplaats je dit getal(2) naar de plaats waar je te sorteren getal staat (1)
4) terug stap 2 tot je niet meer kan
5) waar de index beland is, plaats je het te sorteren getal die op dit moment gesorteerd is.

public void InsertionSort(int[] Tabel)
{
  int X;
  for (int I = 1 ; I < Tabel.Length ; I++)     
  {				                           
    X = Tabel[I];                              
    while ((I - 1 >= 0) && (X < Tabel[I - 1])) 
    {                                          
      Tabel[I] = Tabel[I - 1];                 
      I--;
    }
    Tabel[I] = X;                             
  }
}/*InsertionSort*/

In Python wordt dit:

 def insertionsort(rij):            
     for i in range(len(rij)):         #Overloop kaart per kaart het ongesorteerd gedeelte
         waarde = rij[i]               #Neem kaart i in de rechterhand
         for j in range(0, i):         #Vergelijk de kaart met de kaarten in het gesorteerde deel
             if waarde<rij[j]:         #Heb je de positie van je kaart gevonden, 
                 waarde, rij[j] = rij[j], waarde   #Verwissel die en loop verder met nieuwe kaart
         rij[i] = waarde               #Kaart in rechterhand na overlopen hoort op positie i

Een voorbeeld in JavaScript van insertion sort.

function insertionSort(rij){
		for (var i = 1; i < rij.length ; i++){
			var hulp = rij[i];
			var j = i - 1;
			while (j >= 0 && rij[j] > hulp) { 
				rij[j + 1]= rij[j]; 
				j--;
			}
			rij[j+1] = hulp;
		}
               return rij;
	}