* Wenn `i> =j`, ist die Partitionierung vollständig. Tauschen Sie den Drehpunkt mit "arr [j]" aus. Der Drehpunkt befindet sich jetzt in seiner sortierten Position.
3. Rekursion: Der Algorithmus ruft sich rekursiv auf den beiden Sub-Arrays:
* Das Sub-Array nach * links * des (jetzt sortierten) Drehzahl.
* Das Sub-Array nach * rechts * des (jetzt sortierten) Drehzahl.
Beispiel:
Nehmen wir an, wir haben das Array:`[7, 2, 1, 6, 8, 5, 3, 4]` `
1. Pivot -Auswahl: Pivot =`7` (erstes Element)
2. Partitionierung:
* Initial:`[7, 2, 1, 6, 8, 5, 3, 4]` `
* `Ich beginnt um 2,` J` beginnt um 4.
* `Ich bewegt mich, bis es 8 findet (was> 7).
* `J` bewegt sich, bis es 4 findet (was <=7).
* Swap 8 und 4:`[7, 2, 1, 6, 4, 5, 3, 8]` `
* `Ich bewegt mich, bis es 5 findet.
* `J` bewegt sich, bis es 3 findet.
* Swap 5 und 3:`[7, 2, 1, 6, 4, 3, 5, 8]` `
* `Ich bewegt mich, bis es 5 findet.
* `J` bewegt sich, bis es 3 (wieder) findet.
* i> =j. Swap Pivot (7) mit arr [j] (3):`[3, 2, 1, 6, 4, 7, 5, 8]` `
* Pivot (7) befindet sich jetzt in seiner richtigen Position.
3. Rekursion:
* Quicksort wird auf `[3, 2, 1, 6, 4]` aufgerufen
* Quicksort wird auf `[5, 8]` aufgerufen
Überlegungen zur Visualisierung:
Die Visualisierung müsste zeigen:
* Hervorhebung des Drehes: Geben Sie eindeutig an, welches Element derzeit als Pivot ausgewählt wird. Eine Farbänderung oder ein visuelles Etikett ist üblich.
* Zeigerbewegung: Zeigen Sie visuell die "Ich" und "J` -Zeiger, die sich durch das Array bewegen. Verwenden Sie Pfeile, verschiedene Farben oder andere Indikatoren.
* Swaps: Den Austausch von Elementen animieren. Zum Beispiel könnten die beiden ausgetauschten Elemente in die Positionen des anderen "bewegen".
* Partitionierungsprozess: Betonen Sie, wie die Elemente um den Drehpunkt umgeordnet werden. Dies könnte das Färben von Elementen beinhalten, von denen bekannt ist, dass sie kleiner oder größer sind als der Drehpunkt.
* rekursive Anrufe: Zeigen Sie, wie das Array in Sub-Arrays unterteilt wird und wie der Algorithmus rekursiv auf jedes Sub-Array angewendet wird. Dies kann durch visuell "Verschachteln" der Array -Darstellungen erfolgen. Verwenden Sie möglicherweise unterschiedliche Hintergründe für jede Rekursionsebene.
* sortierte Elemente: Geben Sie an, welche Elemente in ihre endgültigen sortierten Positionen eingesetzt wurden. Verwenden Sie eine eigene Farbe oder einen visuellen Marker.
* Schritt-für-Schritt-Ausführung: Ermöglichen Sie dem Benutzer, den Algorithmus einen Schritt nacheinander zu durchlaufen, damit er jede Aktion deutlich sehen kann.
* Statusinformationen: Zeigen Sie die aktuellen Werte von `I.,` J` und anderen relevanten Variablen an.
Visualisierungstechnologien:
* JavaScript &HTML5 -Leinwand: Eine beliebte Wahl für webbasierte Visualisierungen. Bibliotheken wie D3.Js oder P5.Js können bei den visuellen Elementen helfen.
* Python (mit Bibliotheken wie Pygame oder Matplotlib): Für Desktop -Anwendungen.
* Andere Grafikbibliotheken: Abhängig von der Umgebung können andere Bibliotheken wie Verarbeitung, QT oder OpenGL verwendet werden.
Das Problem mit der Auswahl der Erstelement-Pivot
Obwohl es einfach zu implementieren ist, wählen Sie immer das erste Element, da der Drehpunkt einen erheblichen Nachteil hat:
* Worst-Case-Szenario: Wenn das Array bereits in aufsteigender oder absteigender Reihenfolge sortiert (oder nahezu sortiert) ist, degeneriert der Algorithmus die Zeitkomplexität von O (n^2). Dies liegt daran, dass jede Partition nur ein * Element aus dem Unterarray entfernt wird, was zu sehr unausgeglichenen Partitionen führt.
Beispiel des schlimmsten Falls:
Wenn das Array `[1, 2, 3, 4, 5] ist, und 1 ist immer der Drehpunkt:
1. Pivot =1. Die Partitionierung führt zu `[1, 2, 3, 4, 5]` (1 ist an der richtigen Stelle).
2. rekursiv `[2, 3, 4, 5]` `
3..
4. Rekursiv `[3, 4, 5]` `
... und so weiter.
Der Algorithmus wird im Wesentlichen zu einer sehr ineffizienten Selektionsart.
Wie Visualisierung hilft:
Die Visualisierung zeigt eindeutig dieses schlechteste Verhalten. Sie werden sehen, dass der Partitionierungsprozess lange Zeit dauert, um Elemente zu bewegen, und die rekursiven Anrufe, die sehr unausgeglichene Unterarrays erzeugen. Dies macht es sehr offensichtlich, warum diese einfache Strategie zur Auswahl der Pivot oft nicht die beste Wahl in der Praxis ist. Die Visualisierung kann auch zeigen, wie andere Pivot-Auswahlmethoden (wie die Auswahl eines zufälligen Elements) dieses Worst-Case-Szenario vermeiden können.
