Insertion sort

Insertion Sort is een eenvoudig sorteeralgoritme dat werkt door steeds één element uit de invoerlijst te nemen en het op de juiste positie in een gesorteerde lijst in te voegen. Het begint met een lege gesorteerde lijst en voegt dan geleidelijk één voor één de elementen uit de oorspronkelijke lijst toe aan de gesorteerde lijst.

Hier is een kort overzicht van hoe het werkt:

1. Begin met de tweede element van de lijst (index 1), omdat het eerste element (met index 0) al als een gesorteerde lijst wordt beschouwd.

2. Neem het huidige element en vergelijk het met de elementen in de gesorteerde lijst van rechts naar links.

3. Plaats het huidige element op de juiste positie in de gesorteerde lijst door het te vergelijken met elk element in de gesorteerde lijst en deze naar rechts te schuiven totdat het huidige element op de juiste plaats komt ten opzichte van de andere elementen.

4. Herhaal dit proces voor alle elementen in de oorspronkelijke lijst.

Insertion Sort is efficiënt voor kleine lijsten, maar wordt minder efficiënt naarmate de grootte van de lijst toeneemt, vooral in vergelijking met efficiëntere sorteeralgoritmen zoals Quick Sort of Merge Sort. De tijdscomplexiteit van Insertion Sort is O(n^2) in het slechtste geval en O(n) in het beste geval, waarbij 'n' het aantal elementen in de lijst is.