Hossa 
Sortierverfahren, die auf einem paarweisen Vergleich von Elementen beruhen, sind alle relativ langsam. Bei n Elementen gibt es n! (=Fakultät) Möglichkeiten, diese Elemente anzuordnen. Wenn ich diese n! Kombinationen in einen Entscheidungsbaum packe, dann hat dieser Baum die Höhe log2(n!). Also brauche ich mindestens so viele Vergleiche, um die richtige Kobmination zu finden. Die Mindestanzahl der Vergleiche V(n) beträgt daher:
V(n)=\log_2(n!)
Mit der Stirling-Formel:
n!\approx\sqrt{2\pi,n}\left(\frac{n}{e}\right)^n
Kann man die Anzahl der Vergleiche abschätzen:
V(n)\approx\log_2\left(\sqrt{2\pi,n}\left(\frac{n}{e}\right)^n\right)
V(n)\approx\log_2\left(\sqrt{2\pi,n}\right)+\log_2\left(\left(\frac{n}{e}\right)^n\right)
Den ersten Logarithmus kann man wegen seiner Kleinheit im Vergleich zum zweiten vernachlässigen und erhält dann:
V(n)\approx n\cdot\log_2\left(\frac{n}{e}\right)
Mit dieser Quicksortimplementierung brauche ich für die
gleiche Liste ca. 15 Sekunden.
Quicksort ist wohl das langsamste aller gängigen Sortierverfahren! Im schlimmsten Fall benötigt es sogar n² Vergleiche. Das ist deutlich schlechter als das gerade berechnete theoretische Minimum.
Außerdem habe ich noch die in Python eingebaute
Sortierfunktion .sort() getestet, ich habe gelesen, dass es
sich dabei um eine Version von mergesort handeln soll.
Merge-Sort ist in dem Sinne schneller als Quicksort als dass es auch im schlimmsten Fall n*log(n) Vergleiche benötigt. Aber die Rumkopiererei ist sehr zeitaufwändig.
Wenn mein Algorithmus schneller als der in Python eingebaute
Algorithmus ist, gibt es dennoch einen schnelleren
Algorithmus?
Das schnellste Sortierverfahren, das auf paarweisen Vergleichen von Elementen beruht ist Bottom-up-Heapsort.
Schneller kann man nur noch sortieren, wenn man auf den paarweisen Vergleich der Elemente verzichtet. Es gibt Sortierverfahren, bei denen die Anzahl der benötigten Vergleiche nur linear mit der Anzahl der Elemente ansteigt. Das bekannteste davon ist Bucket-Sort. Es sollen z.B. folgende Zahlen sortiert werden:
167, 157, 121, 942, 237, 558, 333, 721, 49, 888
Beim Bucket-Sort werden 10 Töpfe bereit gestellt, einer für jede der Ziffern 0 bis 9. Beim Sortieren werden im ersten Schritt nur die letzten Ziffern der zu sortierenden Zahlen betrachtet und anhand dieses Kriteriums in die Töpfe geworfen:
Topf 0: —
Topf 1: 121, 721
Topf 2: 942
Topf 3: 333
Topf 4: —
Topf 5: —
Topf 6: —
Topf 7: 167, 157, 237
Topf 8: 558, 888
Topf 9: 49
Danach werden die Zahlen der Reihe nach (die Reihenfolge muss erhalten bleiben) wieder aus den Töpfen genommen. Das ergibt die Reihenfolge:
121, 721, 942, 333, 167, 157, 237, 558, 888, 49
Nun wird der gleiche Vorgang mit der 2-ten Ziffer von rechts durchlaufen:
Topf 0: —
Topf 1: —
Topf 2: 121, 721
Topf 3: 333, 237
Topf 4: 942, 49
Topf 5: 157, 558
Topf 6: 167
Topf 7: —
Topf 8: 888
Topf 9: —
Wieder der Reihe nach rausnehmen:
121, 721, 333, 237, 942, 49, 157, 558, 167, 888
Und nun der letzte Schritt mit der 3-ten Ziffer von rechts, wobei bei der 49 vorne eine „0“ (Null) aufgefüllt wird:
Topf 0: 049
Topf 1: 121, 157, 167
Topf 2: 237
Topf 3: 333
Topf 4: —
Topf 5: 558
Topf 6: —
Topf 7: 721
Topf 8: 888
Topf 9: 942
Rausnehmen und fertig ist die Sortierung:
049, 121, 157, 167, 237, 333, 558, 721, 888, 942
Bucket-Sort beruht nicht auf paarweisen Vergleichen der Elemente und kann daher die Grenze der oben berechneten Mindestanzahl von Vergleichen unterschreiten. Hier werden 3*n Vergleiche benötigt (n Ziffern mit maximal 3 Stellen).
Viele Grüße
Hasenfuß
