In elk fatsoenlijk algoritmenleerboek wordt uitgelegd hoe snel sorteeralgoritmen als quicksort en heapsort zijn, maar je hoeft geen gekke wiskunde uit te voeren om te bewijzen dat ze asymptotisch zo snel zijn als je maar kunt krijgen.
Een pedante noot over notatie
De meeste computerwetenschappers gebruiken big-O notatie voor “asymptotisch gelijk, tot een constante schalingsfactor”, wat het voor andere wiskundigen niet helemaal betekent. Sorry, ik zal big-O gebruiken zoals in CS leerboeken, maar ik zal het tenminste niet verwarren met andere wiskundige notatie.
Comparison-based sorting
Laten we eens kijken naar het speciale geval van algoritmen die waarden twee tegelijk vergelijken (zoals quicksort en heapsort, en de meeste andere populaire algoritmen). De ideeën kunnen later worden uitgebreid tot alle sorteeralgoritmen.
Een eenvoudig telargument voor het slechtste geval
Voorstel dat je een array hebt met vier elementen, allemaal verschillend, in willekeurige volgorde. Kun je die sorteren door slechts een paar elementen te vergelijken? Duidelijk niet, maar hier is een goede reden waarom dat niet kan: Om de matrix te sorteren, moet je per definitie weten hoe je de elementen herschikt om ze op volgorde te zetten. Met andere woorden, je moet weten welke permutatie nodig is. Hoeveel permutaties zijn er mogelijk? Het eerste element kan naar een van de vier plaatsen worden verplaatst, het tweede element naar een van de overige drie, het derde element heeft twee mogelijkheden, en het laatste element moet de enige overblijvende plaats innemen. Er zijn dus 4×3×2×1=4!=244 maal 3 maal 2 maal 1 = 4! = 24 mogelijke permutaties om uit te kiezen, maar er zijn maar twee mogelijke uitkomsten als je twee verschillende dingen vergelijkt: “GROTER” en “KLEINER”. Als je een lijst zou maken van alle mogelijke permutaties, zou je kunnen besluiten dat “GROTER” betekent dat je permutatie #8 nodig hebt en “KLEINER” betekent dat je permutatie #24 nodig hebt, maar je kunt op geen enkele manier weten wanneer je de andere 22 permutaties nodig hebt.
Met twee vergelijkingen, heb je 2×2=42 maal 2 = 4 mogelijke uitkomsten, wat nog steeds niet genoeg is. Je kunt niet elke mogelijke geschudde matrix sorteren, tenzij je minstens vijf vergelijkingen doet (25=322^5 = 32). Als W(N)W(N) het slechtst denkbare aantal vergelijkingen is dat nodig is om NN verschillende elementen te sorteren met een of ander algoritme, dan kunnen we zeggen
2W(N)≥N!2^{W(N)} \Als we een logaritme nemen met basis 2, W(N)≥log2N!W(N)
Asymptotisch gezien, groeit N!N! groeit als NNN^N (zie ook de formule van Stirling), dus
W(N)⪰logNN=NlogNW(N) \succeq \log{N^N} = N\log{N}
En dat is een O(NlogN)O(N\log N) limiet op het ergste geval, alleen al door het tellen van uitgangen.
Gemiddeld geval uit informatietheorie
We kunnen een sterker resultaat krijgen als we dat telargument uitbreiden met een beetje informatietheorie. Zo zouden we een sorteeralgoritme kunnen gebruiken als een code om informatie door te geven:
- Ik denk aan een getal – zeg, 15
- Ik zoek permutatie #15 op uit de lijst van permutaties van vier elementen
- Ik voer het sorteeralgoritme op deze permutatie uit en noteer alle “GROTER” en “KLEINER” vergelijkingsresultaten
- Ik stuur de vergelijkingsresultaten naar jou in binaire code
- Jij speelt mijn sorteeralgoritme na,
- Nu je weet hoe ik mijn array gesorteerd heb, kun je de permutatie omkeren om mijn oorspronkelijke array te achterhalen
- Je zoekt mijn oorspronkelijke array op in de permutatielijst en ziet dat ik het getal 15 heb doorgegeven
Okee, het is een beetje vreemd, maar het is mogelijk. Dat betekent dat sorteeralgoritmen gebonden zijn aan dezelfde wetten als normale codeerschema’s, inclusief de stelling die bewijst dat er geen universele datacompressor is. Ik heb één bit doorgegeven per vergelijking die het algoritme maakt, dus gemiddeld moet het aantal vergelijkingen ten minste gelijk zijn aan het aantal bits dat nodig is om mijn gegevens weer te geven, volgens de informatietheorie. Meer technisch gesproken moet het gemiddelde aantal vergelijkingen ten minste gelijk zijn aan de Shannon-entropie van mijn invoergegevens, gemeten in bits. Entropie is een wiskundige maat voor de informatie-inhoud, of onvoorspelbaarheid, van iets.
Als ik een matrix van NN elementen heb die zonder vertekening in elke mogelijke volgorde kunnen staan, dan is de entropie gemaximaliseerd en islog2N!log_2{N!} bits. Dat bewijst dat O(NlogN)O(Nlog{N}) een optimaal gemiddelde is voor een comparison-based sort met willekeurige invoer.
Dat is de theorie, maar hoe verhouden echte sorteeralgoritmen zich tot elkaar? Hieronder staat een grafiek van het gemiddelde aantal vergelijkingen dat nodig is om een matrix te sorteren. Ik heb het theoretische optimum vergeleken met naïef quicksort en Ford-Johnson merge-insertion sort, dat is ontworpen om vergelijkingen te minimaliseren (hoewel het zelden sneller is dan quicksort omdat er meer in het leven is dan het minimaliseren van vergelijkingen). Sinds de ontwikkeling in 1959 is merge-insertion sort aangepast om er wat meer vergelijkingen uit te halen, maar uit de grafiek blijkt dat het al bijna optimaal is.
Het is leuk als een beetje theorie zo’n strak praktisch resultaat oplevert.
Samenvatting tot nu toe
Hier staat wat tot nu toe is bewezen:
- Als de array in elke volgorde zou kunnen beginnen, zijn er in het ergste geval minstens O(NlogN)O(Nlog{N}) vergelijkingen nodig
- Het gemiddelde aantal vergelijkingen moet ten minste de entropie van de array zijn, en dat is O(NlogN)O(N\log{N}) voor willekeurige invoer
Merk op dat door #2 sorteeralgoritmen op basis van vergelijking sneller kunnen zijn dan O(NlogN)O(N\log{N}) als de invoer een lage entropie heeft (met andere woorden, voorspelbaarder is). Merge sort ligt dicht bij O(N)O(N) als de invoer veel gesorteerde subarrays bevat. Insertion sort ligt dicht bij O(N)O(N) als de invoer een array is dat gesorteerd was voordat het een beetje werd verstoord. Geen van hen verslaat O(NlogN)O(Nlog{N}) in het ergste geval, tenzij sommige array-ordeningen onmogelijk zijn als invoer.
Algemene sorteeralgoritmen
Sorteeralgoritmen op basis van vergelijking zijn in de praktijk een interessant speciaal geval, maar er is theoretisch niets speciaals aanCMP in tegenstelling tot elke andere instructie op een computer. Beide bovenstaande argumenten kunnen veralgemeend worden tot elk sorteeralgoritme als je een paar dingen in acht neemt:
- De meeste computerinstructies hebben meer dan twee mogelijke uitgangen, maar nog steeds een beperkt aantal
- Het beperkte aantal uitgangen betekent dat een instructie slechts een beperkte hoeveelheid entropie kan verwerken
Dat geeft ons dezelfde O(NlogN)O(Nlog{N}) ondergrens aan het aantal instructies. Elke fysiek realiseerbare computer kan maar een beperkt aantal instructies tegelijk verwerken, dus dat is ook een O(NlogN)O(Nlog{N}) ondergrens voor de benodigde tijd.
Maar hoe zit het met “snellere” algoritmen?
De meest bruikbare praktische implicatie van de algemene O(NlogN)O(Nlog{N}) grens is dat als je hoort over een asymptotisch sneller algoritme, je weet dat het op de een of andere manier “vals” moet zijn. Er moet een addertje onder het gras zitten waardoor het geen algemeen sorteeralgoritme is dat schaalt naar willekeurig grote arrays. Het kan nog steeds een bruikbaar algoritme zijn, maar het is een goed idee om de kleine lettertjes goed te lezen.
Een bekend voorbeeld is radix sort. Het wordt vaak een O(N)O(N) sorteeralgoritme genoemd, maar het addertje onder het gras is dat het alleen werkt als alle getallen in kk bits passen, en dat het in werkelijkheid O(kN)O(kN) is.
Wat betekent dat in de praktijk? Stel, je hebt een 8-bit machine. Je kunt 28=2562^8 = 256 verschillende getallen weergeven in 8 bits, dus als je een array van duizenden getallen hebt, krijg je duplicaten. Voor sommige toepassingen is dat prima, maar voor andere moet je upgraden naar minstens 16 bits, waarmee je 216=65.5362^16 = 65.536 getallen duidelijk kunt weergeven. 32 bits ondersteunt 232=4.294.967.2962^32 = 4.294.967.296 verschillende getallen. Naarmate de grootte van de matrix toeneemt, zal het aantal benodigde bits ook toenemen. Om NN verschillende getallen duidelijk weer te geven, heb je k≥log2Nk \geq \log_2{N} nodig. Dus, tenzij je veel duplicaten in je matrix wilt hebben, is O(kN)O(kN) effectief O(NlogN)O(Nlog{N}).
De noodzaak van O(NlogN)O(Nlog{N}) invoergegevens in het algemene geval bewijst eigenlijk het algemene resultaat op zichzelf. Dat argument is in de praktijk niet zo interessant, omdat we zelden miljarden gehele getallen hoeven te sorteren op een 32-bit machine, en als iemand de grenzen van een 64-bit machine heeft bereikt, heeft hij dat de rest van ons niet verteld.