Sorteeralgoritmen vergeleken
Er is niet één snelste sorteeralgoritme. Sommige zijn eenvoudig maar traag, sommige zijn snel op willekeurige gegevens maar struikelen over gesorteerde gegevens, en sommige zijn helemaal geen vergelijkende sorteringen. Als je alle acht op dezelfde lijst laat racen, zie je de verschillen in één oogopslag.
Drie families
Bubblesort, selection sort en insertion sort zijn de eenvoudige sorteringen. Ze vergelijken en verwisselen waarden die dicht bij elkaar staan en hebben op een willekeurige lijst tijd nodig die evenredig is met n². Mergesort, quicksort en heapsort verdelen het werk slim en hebben tijd nodig die evenredig is met n log n, het beste wat een sortering kan als ze alleen mag vragen welke van twee waarden groter is. Radix sort en counting sort slaan die vraag helemaal over: ze gebruiken de cijfers of waarden zelf, wat alleen werkt voor sleutels zoals kleine gehele getallen.
Het werk meten
De sorteerrace telt één operatie voor elke vergelijking, elk gelezen cijfer of elke gelezen waarde, en elke verwisseling of verplaatsing. Bij 40 willekeurige waarden komt dat uit op ongeveer 120 voor counting sort, 240 voor radix sort, 260 voor quicksort, 380 voor mergesort, 490 voor heapsort, ongeveer 820 elk voor selection sort en insertion sort, en meer dan 1.100 voor bubblesort. Echte computers letten ook op geheugen: quicksort is in de praktijk meestal sneller dan zijn telling doet vermoeden, en heapsort trager, door de manier waarop ze door de lijst gaan.
De invoer telt
Bij een bijna gesorteerde lijst heeft insertion sort maar ongeveer 50 operaties nodig voor 40 waarden en bubblesort ongeveer 90, omdat elke waarde dicht bij haar plek staat. Bij een omgekeerde lijst hebben dezelfde twee 1.560 nodig, hun slechtste geval. Selection sort, heapsort, mergesort, radix sort en counting sort maakt de volgorde nauwelijks uit. Quicksort met de mediaan van drie kan goed overweg met gesorteerde en omgekeerde lijsten, maar met een naïeve pivot is een gesorteerde lijst zijn slechtste geval. Weinig unieke waarden vertragen quicksort, omdat gelijke waarden allemaal naar één kant gaan.
Geheugen en stabiliteit
Bubblesort, selection sort, insertion sort, quicksort en heapsort werken in-place, met weinig of geen extra geheugen. Mergesort, radix sort en counting sort hebben een buffer nodig die zo lang is als de lijst. Een stabiele sortering houdt gelijke waarden in hun oorspronkelijke volgorde: bubblesort, insertion sort, mergesort, radix sort en counting sort zijn stabiel, selection sort, quicksort en heapsort niet. Stabiliteit is belangrijk als je records op het ene veld na het andere sorteert.
Welke gebruik je?
In de praktijk gebruik je de sortering die in je programmeertaal is ingebouwd: meestal Timsort, een mergesort die insertion sort gebruikt voor korte stukken en snel is op deels gesorteerde gegevens, of introsort, een quicksort die terugvalt op heapsort en insertion sort gebruikt voor kleine delen. Voor veel kleine gehele sleutels kunnen counting sort of radix sort ze allebei verslaan. Bubblesort en selection sort zijn vooral lesmateriaal.
Probeer het zelf
Open de sorteerrace en druk op Afspelen. Elke baan is één sortering op dezelfde lijst; het getal rechts telt haar operaties, en een baan wordt groen als ze klaar is. Probeer een bijna gesorteerde lijst, een omgekeerde en weinig unieke waarden, en zie de volgorde van finishen veranderen. Elke sortering heeft ook een eigen app, waarin je haar stap voor stap kunt volgen.
Veelgestelde vragen
Wat is het snelste sorteeralgoritme?
Voor algemene gegevens zijn quicksort en mergesort (en hybriden die erop gebouwd zijn, zoals introsort en Timsort) gemiddeld het snelst, met n log n. Voor kleine gehele sleutels zijn counting sort en radix sort nog sneller. Voor korte of bijna gesorteerde lijsten wint insertion sort.
Waarom kan geen vergelijkende sortering n log n verslaan?
Een lijst van n waarden kan in n! volgordes staan, en elke vergelijking heeft twee uitkomsten, dus in het slechtste geval zijn er minstens log₂(n!) vergelijkingen nodig om ze allemaal uit elkaar te houden. Dat is ongeveer n log₂ n. Radix sort en counting sort ontlopen die grens omdat ze niet vergelijken.
Welke sorteeralgoritmen zijn stabiel?
Bubblesort, insertion sort, mergesort, radix sort en counting sort zijn in hun gewone vorm stabiel. Selection sort, quicksort en heapsort niet, omdat ze waarden over grote afstanden verplaatsen.
Welke sorteringen hebben extra geheugen nodig?
Mergesort, radix sort en counting sort hebben een buffer nodig van ongeveer de lengte van de lijst. Bubblesort, selection sort, insertion sort en heapsort hebben bijna niets nodig, en quicksort maar een beetje voor zijn recursie.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Start de sorteerrace