- Zu partitionierender Teil
- Pivot
- Verglichen
- Getauscht
- Platziert
Quicksort
Quicksort wählt ein Pivotelement, setzt alle kleineren Werte davor und alle anderen dahinter und sortiert dann beide Seiten genauso. Nach jeder Partitionierung steht das Pivotelement an seinem endgültigen Platz. Wählen Sie die Pivot-Regel, spielen Sie die Sortierung in beliebigem Tempo ab oder gehen Sie sie Vergleich für Vergleich durch, und sehen Sie, warum ein schlechtes Pivotelement Quicksort bei einer sortierten Liste langsam macht. Drücken Sie „Abspielen“, um die Sortierung anzusehen, oder gehen Sie mit „Schritt“ und „Zurück“ einen Vergleich nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Die Kacheln zählen Vergleiche, Vertauschungen und Partitionierungen. Wählen Sie die Anzahl der Balken und ihre Startreihenfolge, oder geben Sie eigene Zahlen ein, und legen Sie fest, wie das Pivotelement gewählt wird. Ist das Feld ausgewählt, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.
Wie es funktioniert
- Wählen Sie die Anzahl der Balken und ihre Startreihenfolge: zufällig, fast sortiert, umgekehrt oder mit wenigen verschiedenen Werten. Oder geben Sie eigene Zahlen ein.
- Drücken Sie „Abspielen“ oder gehen Sie mit „Schritt“ und „Zurück“ einen Vergleich nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle der Sortierung zu springen.
- Wählen Sie die Pivot-Regel: letzter Wert, mittlerer Wert, zufälliger Wert oder Median aus drei. Probieren Sie jede an einer sortierten Liste aus.
So funktioniert Quicksort
Wählen Sie einen Wert des zu sortierenden Teils als Pivotelement und verschieben Sie ihn ans Ende. Gehen Sie die übrigen Werte von links nach rechts durch; jeder, der kleiner als das Pivotelement ist, wird in einen linken Teil getauscht, der vom Anfang her wächst. Dann tauschen Sie das Pivotelement direkt hinter den linken Teil. Alles davor ist jetzt kleiner und nichts dahinter, also steht das Pivotelement an seinem endgültigen Platz. Sortieren Sie den Teil davor und den Teil dahinter genauso, bis jeder Teil nur noch einen Wert hat.
Warum das Pivotelement zählt
Landet das Pivotelement nahe der Mitte, halbiert jede Partitionierung das Problem, und die Vergleiche wachsen wie n log n: bei 40 zufälligen Werten etwa 190. Ist das Pivotelement der kleinste oder größte Wert, bleibt eine Seite leer und die andere enthält alles Übrige. Mit dem letzten Wert als Pivotelement passiert das bei einer sortierten oder umgekehrten Liste in jedem Schritt, und die Sortierung braucht n(n − 1)/2 Vergleiche, 780 bei 40 Werten. Ein zufälliges Pivotelement oder der Median aus erstem, mittlerem und letztem Wert verhindert das in der Praxis.
Häufig gestellte Fragen
Wie funktioniert Quicksort?
Quicksort wählt ein Pivotelement, partitioniert die Liste so, dass die kleineren Werte vor dem Pivotelement stehen und der Rest dahinter, und sortiert dann beide Seiten mit Quicksort. Nach jeder Partitionierung steht das Pivotelement an seinem endgültigen Platz.
Warum ist Quicksort bei einer sortierten Liste langsam?
Mit dem ersten oder letzten Wert als Pivotelement liefert eine sortierte Liste immer den kleinsten oder größten Wert als Pivotelement. Eine Seite der Partitionierung ist dann leer, jede Partitionierung entfernt also nur einen Wert, und die Sortierung braucht n(n − 1)/2 Vergleiche. Ein zufälliges Pivotelement oder der Median aus drei behebt das in der Praxis.
Ist Quicksort schneller als Mergesort?
In der Praxis oft: Er sortiert in-place, braucht keinen Puffer, und seine innere Schleife ist sehr einfach. Im Mittel macht er etwas mehr Vergleiche als Mergesort, und sein schlimmster Fall ist n², während Mergesort immer n log n braucht. Sortierfunktionen von Bibliotheken wie Introsort beginnen mit Quicksort und wechseln zu Heapsort, wenn die Teilungen zu ungleich werden.
Ist Quicksort stabil?
Nein. Eine Partitionierung tauscht Werte über große Entfernungen, daher können gleiche Werte ihre Reihenfolge ändern.
Werden meine Zahlen irgendwohin gesendet?
Nein. Die Sortierung läuft in Ihrem Browser, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor