25.05.2019Quicksort ist sowohl einer der ältesten als auch einer der schnellsten Algorithmen zur Sortierung: er wurde 1959 von Tony Hoare erfunden. Diese Seite animiert die Ausführungsschritte von Quicksort, aber erst sollte ich die grafischen Elemente vorstellen, die hier benutzt werden. Wir fangen an mit einem Array von Zufallszahlen zwischen 1 und 200. Die Zahlen werden unten im Diagramm angezeigt, mit Säulen darüber die die Größe der Zahl wiederspiegeln.
Ein Schlüsselelement von Quicksort ist die Verwendung von (engl.) ‘Pivots’. Hier ist das erste Element als Pivotelement ausgewählt worden, was eine gültige Wahl ist. Später besprechen wir zufällige Pivots. Das Pivot ist also rot markiert, und die wichtigste Eigenschaft ist die Größe, was hier durch die rote Linie angedeutet wird. Jetzt sollen alle Elemente die kleiner oder gleich dem Pivot sind auf die linke Seite des Arrays platziert werden und alle Elemente die größer sind, sollen auf die rechte Seite. Dann wird der Pivot in die Mitte der beiden Seiten gesetzt.
Dieses Panel zeigt die Partitionierung wie schon besprochen. Die grünen Quadrate enthalten Zahlen kleiner als oder gleich dem Pivot Element (rot) und die blauen Quadrate enthalten größere Zahlen. Wenn der Algorithmus sich von links nach rechts bewegt, werden Elemente getauscht um grün von blau zu trennen. Nachdem der Pivot zwischen die Segmente platziert wird, nimmt es seine endgültige Position im Array ein! Es ist also bereits ein Element an die richtige Stelle fertig sortiert worden.
Quicksort ist ein ‘teile und herrsche’ Algorithmus (engl. ‘divide and conquer’), eine häufige Strategie für Algorithmen. Jetzt da die Zahlen partitioniert sind, wird das Array in die grüne und blaue Hälfte aufgeteilt, um diese getrennt wieder zu partitionieren. Dies wird auf beiden Seiten rekursiv wiederholt, so lange bis die Arrays nur ein Element lang sind. Zu diesem Zeitpunkt ist dann das ganze Array sortiert. Da die Unterarrays im Allgemeinen nicht von gleicher größe sind, oft weit gefehlt, kann diese rekursive Teilung oft recht beliebig aussehen.
Auf Englisch heißt es ‘worst-case behaviour’, eine Situation in der der Algorithmus Probleme hat. Obwohl Quicksort mit den bisher eingegebenen zufälligen Zahlen recht schnell ist, können bestimmte Eingaben zu viel langsamerem vorgehen führen. Hier fangen wir mit einem Array von monoton fallenden Zahlen an. Die einfachste Art sie zu sortieren, wäre natürlich den Array in seiner Reihenfolge umzudrehen. Aber Quicksort partitioniert die Daten nicht gut, was zu einer langsamen vorgehensweise führt. Vergleichen Sie einfach mal die Geschwindigkeit auf diesem Panel mit dem vorherigen.
Eine Lösung für das oben beschriebenen Problem ist, ein zufälliges Element als Pivot auszuwählen. Nach der Wahl wird der Pivot an die erste Stelle des Unterarrays getauscht, und dann kann die Partitionierung wie zuvor durchgeführt werden und die Sortierung schreitet schneller voran, für die schwierige Eingabe.
Zum Spaß sortieren wir mal einen etwas größeren Array, einen der gut auf den Bildschirm passt, ohne alle Details zu verbergen. Hier sind 101 Zufallszahlen, wieder zwischen 1 und 200. Die Animationsgeschwindigkeit ist um den Faktor 2,5 erhöht, also nicht so viel. Wir sehen, dass das Array wieder relativ schnell sortiert wird. Dies liegt daran, dass Quicksort mit größeren Arrays gut skaliert.
Es gibt mehr zu Algorithmen und Datenstrukturen auf unserer Hauptseite zu entdecken. Die Seite über den Heap enthält ein Panel über Heapsort, einem anderen aber ähnlich effizienten Sortieralgorithmus.