Bubblesort is eenvoudig te begrijpen, maar het is een bruteforcetechniek: het voert alle vergelijkingen uit, ook als dat niet nodig is. Voor een rij van 5 namen valt dat best mee, maar voor een lijst van duizenden elementen wordt dat traag: het aantal vergelijkingen groeit ongeveer met het kwadraat van het aantal elementen.

Andere sorteeralgoritmen, zoals quicksort en mergesort, presteren doorgaans veel beter op grote lijsten. Ze zijn geen bruteforcetechnieken, maar verdeel-en-heers algoritmen.

In deze leesactiviteit leer je het idee achter die snellere algoritmen kennen. Je hoeft ze niet zelf te programmeren; het gaat om de techniek erachter.

Verdeel en heers

Verdeel en heers is een algoritmische techniek waarbij je een probleem opsplitst in kleinere, beter behapbare deelproblemen. Je lost die deelproblemen apart op en je combineert hun oplossingen tot het antwoord op het oorspronkelijke probleem. Door een groot probleem zo te reduceren tot eenvoudiger deelproblemen, los je het vaak veel sneller op.

Twee klassieke sorteeralgoritmen passen deze techniek toe.

Mergesort

Mergesort verdeelt de lijst in kleinere stukken, sorteert die apart en voegt ze daarna samen tot één gesorteerde lijst:

1. Verdeel de lijst in twee helften.
2. Pas mergesort recursief toe op elke helft (verdeel die op hun beurt verder, tot je stukjes van één element overhoudt; die zijn vanzelf gesorteerd).
3. Voeg de twee gesorteerde helften samen tot één gesorteerde lijst.

Quicksort

Quicksort kiest een pivot (spilelement) en verdeelt de lijst rond die pivot:

1. Kies een pivot (bijvoorbeeld het middelste element).
2. Verdeel de lijst in twee delen: de elementen kleiner dan de pivot en de elementen groter dan of gelijk aan de pivot.
3. Pas quicksort recursief toe op beide delen.
4. Combineer de gesorteerde delen en de pivot tot de volledige gesorteerde lijst.

Het patroon

Merk op dat beide algoritmen hetzelfde stramien volgen: een groot probleem opsplitsen, de stukken apart oplossen (vaak recursief, zoals je leerde in het hoofdstuk over recursie) en de oplossingen samenvoegen. Dat is precies de kracht van verdeel en heers.

Dezelfde verdeel-en-heers-techniek zit ook achter het binair zoeken, dat we in de volgende leesactiviteit bekijken. Daar splits je niet om te sorteren, maar om snel een element terug te vinden in een gesorteerde lijst.