Welke algoritmes lijken sneller te werken en wanneer?

Selection Sort vs. Insertion Sort

Bij Selection Sort zien we dat er een duidelijk verband is tussen de lengte van de lijst en de uitvoertijd. Dit verband lijkt minder te bestaan bij Insertion Sort.

Waarom is dat zo?

Selection Sort volgt voor alle lijsten met hetzelfde aantal elementen altijd exact dezelfde stappen, ongeacht de oorspronkelijke volgorde. De uitvoertijd is dus heel voorspelbaar en constant voor een bepaalde lijstlengte.

Insertion Sort heeft een variabel aantal stappen nodig, afhankelijk van de volgorde van de elementen:

• Als de lijst al bijna gesorteerd is, hoeven elementen nauwelijks te verplaatsen → snel ⚡
• Als de lijst omgekeerd gesorteerd is, moet elk element langs alle vorige elementen → traag 🐌

🤔 Huh? – Wanneer gebruik je welk algoritme?

• Gebruik Selection Sort als je een voorspelbare uitvoertijd wil, ongeacht de input.
• Gebruik Insertion Sort als je lijst al grotendeels gesorteerd is, dan is het veel sneller dan Selection Sort!

🧠 Denkoefening – Welk algoritme is het snelste?

Welk algoritme zal het efficiëntste zijn voor de volgende lijsten?

1. Een volledig willekeurige lijst
2. Een al gesorteerde lijst
3. Een omgekeerd gesorteerde lijst

🧐 Wist je dat…

…er algoritmes bestaan die nog sneller sorteren dan Selection Sort en Insertion Sort? Bij deze algoritmes leidt een verdubbeling van de lijstlengte tot maar iets meer dan een verdubbeling van de uitvoertijd — in plaats van een verviervoudiging. In het volgende hoofdstuk bespreken we enkele van deze algoritmes.

Toepassingen

Sorteeralgoritmes zijn overal aanwezig in het dagelijkse leven:

• Spotify toont voor elk land een lijst met de meest beluisterde liedjes. Om dit te tonen, moet Spotify de lijst sorteren volgens het aantal keren dat elk liedje beluisterd is.
• bol.com laat je producten sorteren van meest naar minst populair, van goedkoopst naar duurste, enzovoort.