Bij insertion sort wordt de lijst ook opgesplitst in twee delen:
een gesorteerd deel (aanvankelijk leeg) en een ongesorteerd deel.
In dit geval neem je steeds een element uit het ongesorteerde deel van de lijst en voeg je dit op de juiste plaats toe aan het gesorteerde deel.
Bekijk de video over het insertion sort algoritme.
Het insertion sort algoritme zou je op de volgende manier kunnen beschrijven:
doorloop vanaf element 2 het ongesorteerde deel van de lijst
pak het huidige element en zet het in tijdelijk
schuif vanaf het laatste element in de gesorteerde lijst tot
aan het element dat kleiner is dan tijdelijk
In Java ziet de programmacode voor het sorteren van een rij getallen met insertion sort er als volgt uit:
public void insertionSort(int[] rij) {
for (int teller = 1; teller < MAXAANTAL; teller++ ) {
int tijdelijk = rij[teller];
int loper = teller - 1;
while((loper >= 0) && (tijdelijk < rij[loper])) {
rij[loper+1] = rij[loper];
loper--;
}
rij[loper+1] = tijdelijk;
}
}