Insertion sort

Insertion sort is hoe de meeste mensen een hand kaarten sorteren: pak de volgende kaart en schuif die op de juiste plek tussen de kaarten die al op volgorde liggen. Het is traag bij lange willekeurige lijsten, maar heel snel bij korte of bijna gesorteerde, en daarom gebruiken echte sorteerbibliotheken het nog steeds.

Staven die gesorteerd worden, met links een gesorteerd deel en één staaf die er langs de grotere staven in terugschuift
Staven die gesorteerd worden, met links een gesorteerd deel en één staaf die er langs de grotere staven in terugschuift

Het idee

Houd het begin van de lijst gesorteerd. In het begin is dat gesorteerde deel alleen de eerste waarde. Neem de volgende waarde en vergelijk die met de waarde ervoor. Is die groter, verwissel ze dan en vergelijk opnieuw, één plek verder terug. Stop als de waarde ervoor niet groter is, of als de waarde vooraan staat. Het gesorteerde deel is één waarde gegroeid. Herhaal dit met elke waarde tot het eind.

Een voorbeeld

Neem 5, 1, 4, 2, 8. Ronde 1 neemt 1: 5 is groter, dus ze wisselen, en 1 komt vooraan: 1, 5, 4, 2, 8. Ronde 2 neemt 4: die wisselt met 5 en stopt dan bij 1: 1, 4, 5, 2, 8. Ronde 3 neemt 2: die wisselt met 5 en met 4 en stopt dan bij 1: 1, 2, 4, 5, 8. Ronde 4 neemt 8, die al groter is dan 5, dus één vergelijking is genoeg. Dat zijn 7 vergelijkingen en 4 verwisselingen. Bubblesort heeft op dezelfde lijst 9 vergelijkingen nodig, selection sort 10.

Verwisselingen zijn gelijk aan inversies

Een inversie is een paar waarden in de verkeerde volgorde. Twee buren die verkeerd staan verwisselen haalt precies één inversie weg, en insertion sort verwisselt alleen zulke buren. Het doet dus precies zoveel verwisselingen als de beginlijst inversies heeft, evenveel als bubblesort. Elke ronde doet ook hoogstens één vergelijking die niet tot een verwisseling leidt: de vergelijking die de ronde stopt. Het aantal vergelijkingen is dus het aantal inversies plus hoogstens n − 1.

Adaptief: snel als de lijst bijna gesorteerd is

Omdat het werk gelijk is aan het aantal inversies plus ongeveer n, is insertion sort snel zodra er weinig inversies zijn. Een gesorteerde lijst kost n − 1 vergelijkingen en geen verwisselingen. Een lijst waarin elke waarde maar een paar plekken van zijn plaats staat, kost tijd dicht bij n. Alleen een lijst die ver van gesorteerd is, zoals een omgekeerde met n(n − 1)/2 inversies, kost tijd evenredig met n². Bij een willekeurige lijst zijn het gemiddeld ongeveer n²/4 verwisselingen.

Waar het gebruikt wordt

Insertion sort is stabiel, heeft geen extra geheugen nodig en heeft heel weinig overhead. Bij korte lijsten verslaat het algoritmen die op papier sneller zijn. Veel sorteerfuncties in bibliotheken, zoals Timsort in Python en Java en de introsort in C++, schakelen voor kleine stukken van de lijst over op insertion sort, meestal tot enkele tientallen waarden. Het past ook bij gegevens die één voor één binnenkomen, omdat elke nieuwe waarde meteen kan worden ingevoegd.

Probeer het zelf

Open de app en druk op Afspelen, of druk op Stap om per vergelijking te gaan. De waarde die wordt ingevoegd heeft een eigen kleur, de waarde waarmee die wordt vergeleken is gemarkeerd en het gesorteerde deel is groen. Anders dan bij bubblesort en selection sort is het groene deel niet definitief: een latere, kleinere waarde kan er nog in schuiven. Probeer een bijna gesorteerde lijst om te zien hoe kort de rondes zijn, en daarna een omgekeerde.

Veelgestelde vragen

Wat is de tijdcomplexiteit van insertion sort?

O(n²) in het slechtste en gemiddelde geval, en O(n) in het beste geval: een lijst die al gesorteerd is. Preciezer: de tijd is evenredig met n plus het aantal inversies. Er is maar O(1) extra geheugen nodig.

Wat is het verschil tussen insertion sort en selection sort?

Selection sort doorzoekt het hele ongesorteerde deel naar de kleinste waarde, dus doet het altijd n(n − 1)/2 vergelijkingen maar weinig verwisselingen. Insertion sort neemt de volgende waarde zoals die komt en schuift die maar zo ver terug als nodig, dus doet het minder vergelijkingen, vooral bij bijna gesorteerde lijsten, maar meer verwisselingen.

Wat is binary insertion sort?

Een variant die met binair zoeken in het gesorteerde deel bepaalt waar de nieuwe waarde hoort. Dat kost ongeveer log n vergelijkingen in plaats van tot n. De waarden moeten nog steeds opschuiven om ruimte te maken, dus het aantal verplaatsingen, en het slechtste geval O(n²), blijven gelijk.

Is insertion sort stabiel?

Ja. Een waarde schuift alleen terug langs waarden die strikt groter zijn, dus gelijke waarden houden hun oorspronkelijke volgorde.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Probeer insertion sort