If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

Partitionieren in Linearzeit

Bei Quicksort erfolgt die eigentliche Arbeit während des Teile-Schritts, welcher das Array array [p..r] um ein Pivot partitioniert, das aus dem Subarray stammt. Obwohl wir jedes Element im Subarray als Pivot wählen könnten, ist es am einfachsten, die Partitionierung so zu implementieren, dass wir das am weitesten rechts liegende Element des Subarrays, A [r], als Pivot wählen.
Nachdem wir ein Pivot gewählt haben, partitionieren wir das Subarray, indem wir es von links nach rechts durchgehen, wobei jedes Element mit dem Pivot verglichen wird. Wir pflegen zwei Indizes q und j im Subarray, das es in vier Gruppen aufteilt. Wir verwenden den Variablennamen q, weil dieser Index irgendwann auf unser Pivot zeigen wird. Wir verwenden j, weil es ein gewöhnlicher Zähler-Variablenname ist, und die Variable verworfen wird, sobald wir fertig sind.
  • Die Elemente in array [p..q-1] bezeichnen wir als "Gruppe L", bestehend aus Elementen, die k l einer oder gleich dem Pivot sind.
  • Die Elemente in array[q..j-1] sind "Gruppe G," bestehend aus Elementen, die g rößer als Pivot sind.
  • Die Elemente in array [j..r-1] sind "Gruppe U", bestehend aus Elementen, deren Beziehung zum Pivot u nbekannt ist, weil sie noch nicht verglichen wurden.
  • Schließlich ist array[r] die "Gruppe P", das P ivot.
Anfänglich sind q und j gleich p. Bei jedem Schritt vergleichen wir A[j], das am weitesten links stehende Element in der Gruppe U, mit dem Pivot. Wenn A [j] größer als Pivot ist, dann inkrementieren wir j, so dass der Trennstrich zwischen den Gruppen G und U eine Position nach rechts wandert:
Ein Diagramm, das einen Schritt der Partitionierung eines Subarrays zeigt. Das Subarray beginnt mit dem Index p und vier Items in der Gruppe L, dann mit dem Index q und sechs Items in der Gruppe G, dann mit dem Index j und fünf Items in der Gruppe U und schließlich mit dem Index r. Nach dem Schritt ist das Subarray fast gleich, aber die Gruppe G hat sieben Items, die Gruppe U hat vier Items und der Index j zeigt auf das erste Item der Gruppe U.
Wenn stattdessen A[j] kleiner oder gleich dem Pivot ist, dann tauschen wir A[j] mit A[q] (dem am weitesten links stehende Element in Gruppe G), inkrementieren j und q, wodurch die Trennlinien zwischen den Gruppen L und G und G und U eine Position nach rechts wandert:
Ein Diagramm, das einen Schritt der Partitionierung eines Subarrays zeigt. Das Subarray beginnt mit dem Index p und vier Elementen in der Gruppe L, dann mit dem Index q und sechs Elementen in der Gruppe G, dann mit dem Index j und fünf Elementen in der Gruppe U und schließlich mit dem Index r. Nach dem Schritt hat das Subarray nun fünf Elemente in der Gruppe L (das letzte Element hält den vorherigen Wert des Elements bei Index j) und vier Elemente in der Gruppe U.
Sobald wir den Drehpunkt erreicht haben, ist die Gruppe U leer. Wir tauschen den Drehpunkt mit dem am weitesten links stehenden Element der Gruppe G: Tausche A[r] mit A[q]. Dieser Tausch setzt den Pivot zwischen die Gruppen L und G und macht das Richtige, auch wenn die Gruppe L oder die Gruppe G leer ist.
Die Funktion partition, die diese Idee umsetzt, gibt auch den Index q zurück, wo sie den Pivot platziert hat, so dass die Funktion quicksort, die sie aufruft, weiß, wo die Partitionen sind.
Hier sind die Schritte zur Partitionierung des Subarrays [12, 7, 14, 9, 10, 11] in array[4..9]:
Die Partitionierung eines Subarrays mit n Elementen nimmt Θ(n) Zeit in Anspruch. Jedes Element A[j] wird einmal mit dem Pivot verglichen. A[j] kann, aber muss nicht mit A[q] vertauscht werden, q wird vielleicht inkrementiert, und j wird immer inkrementiert. Die Gesamtzahl der Programmzeilen, die pro Element des Subarrays ausgeführt werden, ist weitgehend konstant. Da das Subarray n -Elemente hat, ist die benötigte Zeit zum Partitionieren Θ(n), also linear.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.

Willst du an der Diskussion teilnehmen?

Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.