Gibt es bessere Sortieralgorithmen als Quicksort?
Definiere besser.
Möchten wir die Komplexität im besten, schlechtesten oder durchschnittlichen Fall betrachten? Muss das Verfahren stabil sein? Muss der Algorithmus in situ sein? Wieviel zusätzlichen Speicher haben wir zur Verfügung? Wie groß ist die Datenmenge?
Kein vergleichsbasiertes Sortierverfahren kann eine worst-case Komplexität von weniger als
O(nlogn)
haben. Quicksort hat
O(nlogn)
im durchschnittlichen Fall, aber
O(
n
2
)
im schlechtesten Fall. Üblicherweise nicht stabil, stabile Varianten existieren aber. Platzkomplexität im schlechtesten Fall ist
O(n)
.
Merge Sort läuft in
O(nlogn)
sowohl im besten, im durchschnittlichen, als auch im schlechtesten Fall. Der konstante Vorfaktor ist üblicherweise höher als bei Quicksort. Ist stabil und lässt sich gut parallelisieren. Kann man auch in situ machen, dann aber im schlechtesten Fall etwas langsamer.
Heapsort hat ebenfalls eine garantierte Laufzeit von
O(nlogn)
, wenn auch in der Praxis meistens etwas langsamer als Quicksort. Nicht stabil. Platzkomplexität
O(1)
.
Nicht-vergleichsbasierte Sortieralgorithmen lassen sich oft nicht so einfach vergleichen. Radix Sort zum Beispiel hat eine Zeitkomplexität von
O(nw)
, wobei
n
die Anzahl und
w
die Länge der Schlüssel ist. Ob das jetzt schneller als
O(nlogn)
ist, kommt auf ein paar zusätzliche Annahmen an. Für große
n
und konstantes
w
auf jeden Fall. Wenn alle Schlüssel unterschiedlich sind, muss
w
mindestens
logn
sein, was höchstens genauso effizient wie vergleichsbasierte Verfahren macht.
Bucket Sort hat eine average-case-Komplexität von
O(n+
n
2
k
+k)
, was bei einer Gleichverteilung
O(n)
entspricht. Im schlechtesten Fall (wenn alle Werte im gleichen Bucket landen) wird die Laufzeit des Algorithmus von der Laufzeit des sekundären Sortieralgorithmus dominiert, im Falle von Merge Sort also zum Beispiel
O(nlogn)
(wobei üblicherweise Insertion Sort benutzt wird, dann
O(
n
2
)
). Speicherbedarf ist
O(n)
.
Daneben gibt es natürlich noch wesentlich mehr und insbesondere Hybride der oben genannten machen manchmal Sinn. Was genau jetzt der beste Algorithmus ist, kommt, wie so oft, auf die Anwendung an.
Nimm einfach nur nicht Bogosort.