Kun je algoritmen noemen waarvan de asymptotische complexiteit beter is dan die van quicksort?

De quicksort werkt gemiddeld in O(n log n), wat de optimale asymptotiek is voor vergelijkingsalgoritmen. Er zijn echter algoritmen met een betere asymptotische complexiteit in sommige gevallen:

• Telling Sorteer (Counting Sort) — O(n + k), waarbij k het bereik van waarden is. Werkt sneller als k niet te groot is.
• Radix Sorteer (Radix Sort) — O(d * (n + k)), waarbij d het aantal cijfers is, k de basis van het getalsysteem. Efficiënt voor het sorteren van nummers of strings.
• Samenvoeg Sorteer (Merge Sort) — gegarandeerd O(n log n), stabiel en voorspelbaar.

Belangrijk: algoritmen met een betere dan O(n log n) complexiteit zijn niet gebaseerd op het vergelijken van elementen, maar gebruiken aanvullende aannames over de gegevens (bijvoorbeeld een beperkt bereik van waarden).