Insertion sort is een eenvoudig sorteeralgoritme dat werkt door telkens één element uit de ongesorteerde sectie van de lijst te nemen en het op de juiste positie in de gesorteerde sectie van de lijst in te voegen. Het begint met een gesorteerde sectie van één element (het eerste element van de lijst) en voegt vervolgens één voor één de overige elementen toe aan de gesorteerde sectie, waarbij de elementen op de juiste plaats worden ingevoegd. Via deze link krijg je een visuele voorstelling van het insertion sort algoritme.
Hier is een stapsgewijze uitleg van het insertion sort algoritme:
Schrijf een functie insertionsort met een lijst van getallen als parameter die een gesorteerde lijst als returnwaarde heeft.
>>> insertionsort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]
>>> insertionsort([73, 41, 74, 72, 8, 10, 57, 84, 68, 21])
[8, 10, 21, 41, 57, 68, 72, 73, 74, 84]