Sortierverfahren im Vergleich
Das eine schnellste Sortierverfahren gibt es nicht. Manche sind einfach, aber langsam, manche sind schnell bei zufälligen Daten, stolpern aber über sortierte, und manche sortieren gar nicht durch Vergleiche. Ein Rennen aller acht auf derselben Liste zeigt die Unterschiede auf einen Blick.
Drei Familien
Bubblesort, Selectionsort und Insertionsort sind die einfachen Verfahren. Sie vergleichen und tauschen nahe beieinanderliegende Werte und brauchen auf einer zufälligen Liste Zeit proportional zu n². Mergesort, Quicksort und Heapsort teilen die Arbeit geschickt auf und brauchen Zeit proportional zu n log n. Schneller geht es nicht, wenn ein Verfahren nur fragen darf, welcher von zwei Werten größer ist. Radixsort und Countingsort lassen diese Frage ganz weg: Sie nutzen die Ziffern oder Werte selbst, was nur bei Schlüsseln wie kleinen ganzen Zahlen funktioniert.
Die Arbeit messen
Das Sortier-Wettrennen zählt eine Operation für jeden Vergleich, jede gelesene Ziffer, jeden gelesenen Wert und jede Vertauschung oder Verschiebung. Bei 40 zufälligen Werten ergibt das etwa 120 für Countingsort, 240 für Radixsort, 260 für Quicksort, 380 für Mergesort, 490 für Heapsort, je etwa 820 für Selectionsort und Insertionsort und über 1.100 für Bubblesort. Echte Computer achten auch auf den Speicher: Quicksort ist in der Praxis meist schneller, als seine Zählung vermuten lässt, und Heapsort langsamer, weil sie sich unterschiedlich durch die Liste bewegen.
Die Eingabe zählt
Bei einer fast sortierten Liste braucht Insertionsort für 40 Werte nur etwa 50 Operationen und Bubblesort etwa 90, weil jeder Wert nahe an seinem Platz steht. Bei einer umgekehrten Liste brauchen dieselben beiden 1.560, ihr schlimmster Fall. Selectionsort, Heapsort, Mergesort, Radixsort und Countingsort ist die Reihenfolge fast egal. Quicksort mit dem Median aus drei kommt mit sortierten und umgekehrten Listen gut zurecht, aber mit einem naiven Pivot ist eine sortierte Liste sein schlimmster Fall. Wenige verschiedene Werte bremsen Quicksort, weil gleiche Werte alle auf eine Seite gehen.
Speicher und Stabilität
Bubblesort, Selectionsort, Insertionsort, Quicksort und Heapsort arbeiten in-place, mit wenig oder gar keinem zusätzlichen Speicher. Mergesort, Radixsort und Countingsort brauchen einen Puffer, der so lang ist wie die Liste. Ein stabiles Verfahren lässt gleiche Werte in ihrer ursprünglichen Reihenfolge: Bubblesort, Insertionsort, Mergesort, Radixsort und Countingsort sind stabil, Selectionsort, Quicksort und Heapsort nicht. Stabilität ist wichtig, wenn Sie Datensätze nacheinander nach mehreren Feldern sortieren.
Welches Verfahren passt
In der Praxis nehmen Sie das Sortierverfahren, das in Ihre Programmiersprache eingebaut ist: meist Timsort, ein Mergesort, der für kurze Stücke Insertionsort nutzt und bei teilweise sortierten Daten schnell ist, oder Introsort, ein Quicksort, der auf Heapsort ausweicht und für kleine Teile Insertionsort nutzt. Bei vielen kleinen ganzzahligen Schlüsseln können Countingsort oder Radixsort beide schlagen. Bubblesort und Selectionsort dienen vor allem dem Lernen.
Selbst ausprobieren
Öffnen Sie das Sortier-Wettrennen und drücken Sie „Abspielen“. Jede Bahn ist ein Verfahren auf derselben Liste; die Zahl rechts zählt seine Operationen, und eine Bahn wird grün, wenn sie fertig ist. Probieren Sie eine fast sortierte Liste, eine umgekehrte und wenige verschiedene Werte, und beobachten Sie, wie sich die Reihenfolge im Ziel ändert. Jedes Verfahren hat auch eine eigene App, in der Sie es Schritt für Schritt verfolgen können.
Häufig gestellte Fragen
Welches Sortierverfahren ist am schnellsten?
Bei allgemeinen Daten sind Quicksort und Mergesort (und darauf aufbauende Hybride wie Introsort und Timsort) im Durchschnitt am schnellsten, mit n log n. Bei kleinen ganzzahligen Schlüsseln sind Countingsort und Radixsort noch schneller. Bei kurzen oder fast sortierten Listen gewinnt Insertionsort.
Warum kann kein vergleichsbasiertes Verfahren n log n schlagen?
Eine Liste aus n Werten kann in n! Reihenfolgen vorliegen, und jeder Vergleich hat zwei Ausgänge. Also braucht es im schlimmsten Fall mindestens log₂(n!) Vergleiche, um alle zu unterscheiden. Das sind etwa n log₂ n. Radixsort und Countingsort umgehen diese Grenze, weil sie nicht vergleichen.
Welche Sortierverfahren sind stabil?
Bubblesort, Insertionsort, Mergesort, Radixsort und Countingsort sind in ihrer üblichen Form stabil. Selectionsort, Quicksort und Heapsort nicht, weil sie Werte über weite Strecken verschieben.
Welche Verfahren brauchen zusätzlichen Speicher?
Mergesort, Radixsort und Countingsort brauchen einen Puffer, der etwa so lang ist wie die Liste. Bubblesort, Selectionsort, Insertionsort und Heapsort brauchen fast keinen, und Quicksort nur ein wenig für seine Rekursion.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Sortier-Wettrennen starten