Vor kurzem habe ich zwei grundlegende Algorithmen beschrieben, die benutzt werden können, um eine Menge von Daten zu sortieren. Betrachtet wurden Bubblesort und Selectionsort, wobei für beide Algorithmen festgestellt wurde, dass sie relativ ineffizient sind, was ihr Sortierverhalten angeht. Für den Einsatz in Programmen, wo Geschwindigkeit wichtig ist und große Datenmengen sortiert werden müssen, können sie daher nicht wirklich eingesetzt werden. Man benötigt demzufolge Algorithmen, die etwas effizienter arbeiten als die beiden bereits vorgestellten. Der bekannteste und am häufigsten verwendete Algorithmus ist hier zweifelsohne der von Tony Hoare entwickelte Quicksort-Algorithmus, und um den soll es jetzt gehen.
Bevor wir uns den Algorithmus selber anschauen, muss allerdings vorher noch schnell eine (zum Glück relativ einfache) Programmiertechnik erklärt werden, nämlich die der Rekursion. Unter Rekursion versteht man in der Informatik die Technik, ein bestimmtes Konzept (also etwa eine Funktion) mit veränderten Eingabedaten
auf sich selbst
anzuwenden. Zur Einstimmung ein kurzes Beispiel. Jedem dürfte die Summen-Funktion sum ein Begriff sein, welche für eine gegebene natürliche Zahl n die Summe aller natürlichen Zahlen von 0 bis einschließlich n berechnet; so ist etwa sum(4) = 1 + 2 + 3 + 4 = 10. In einem Programm lässt sich diese Funktion zum einen iterativ, also in aufeinanderfolgenden Schritten berechnen; der Programmcode hierfür sähe zum Beispiel so aus:
(2) s ∈ N, s ← 0
(3) for i from 1 to n:
(4) s ← s + i
(5) return s
Der Code ist relativ einfach; es wird einfach ausgehend von einem Startwert 0 jede Zahl von 1 bis n auf das Ergebnis addiert und dieses im Anschluss zurückgegeben. Die gleiche Funktion lässt sich nun allerdings auch rekursiv berechnen, indem die Funktion wiederholt auf sich selbst angewendet wird. Der Code dafür könnte so aussehen:
(2) if n = 0:
(3) return 0
(4) else:
(5) return n + sum( n – 1 )
Wichtig für jede Rekursion ist das Vorhandensein eines Rekursionendes. In obigem Beispiel wäre das in den Zeilen 2 und 3 zu finden, nämlich dann, wenn die aufzusummierende Zahl 0 ist; dann wird einfach fest der Wert 0 selber zurückgegeben. In jedem anderen Fall wird das Ergebnis aus der Addition der betrachteten Zahl mit dem Ergebnis der Summenberechnung für die nächstkleinere Zahl zurückgegeben. Dröselt man diese rekursive Anwendung der Funktion zum Beispiel für die Eingabe 3 auf, so ergibt sich die folgende Funktionskette:
sum(3) = 3+sum(2) = 3+2+sum(1) = 3+2+1+sum(0) = 3+2+1+0 = 6
Mit diesem Wissen gewappnet können wir uns nun anschauen, wie mit Hilfe der Rekursion eine Eingabemenge sortiert werden kann. Der Quicksort-Algorithmus ist ein sogenannter Divide and conquer (teile und herrsche)-Algorithmus, bei welchem ein zu lösendes Problem in immer kleinere Teilprobleme zerlegt wird, bis die Teilprobleme einfach gelöst und die Lösungen zur Gesamtlösung kombiniert werden können.
Für Quicksort bedeutet das, dass die zu sortierende Datenmenge in zwei kleinere Mengen aufgeteilt wird, wobei die Elemente der einen Menge alle kleiner sind als die Elemente der anderen Menge. Zu diesem Zweck wird ein sogenanntes Pivot-Element in der Datenmenge ausgewählt und die Datenmenge anschließen so umsortiert, dass sich links vom Pivot-Element nur Elemente kleiner, rechts davon nur Element größer als das Pivot-Element befinden – das Pivot-Element befindet sich damit also an seiner abschließenden Stelle für die sortierte Datenmenge. Anschließend werden die Teilmengen links und rechts vom Pivot-Element rekursiv weiter umgeordnet; dies geschieht so lange, bis die gesamte Datenmenge sortiert ist. Der Algorithmus besteht also im wesentlichen aus drei Teilen: der Wahl eines Pivot-Elementes (choose), der Umsortierung der Datenmenge, so dass sich links vom Pivot-Element nur kleinere, rechts davon nur größere Elemente befinden (partition) sowie der rekursiven Anwendung des Sortierungfunktion (quicksort). Schreiben wir den Code dafür auf, so ergibt sich das folgende Bild (die Variablen left und right beschreiben die Grenzen des lokal zu sortierenden Feldes):
(2) if left < right:
(3) index ∈ N, index ← partition( a, left, right )
(4) quicksort( a, left, index – 1 )
(5) quicksort( a, index + 1, right )
(6)
(7) partition: a ∈ Nn × left, right ∈ N → N:
(8) pivotIndex ∈ N, pivotIndex ← choose( a, left, right )
(9) pivot ∈ N, pivot ← a[pivotIndex]
(10) swap( a[pivotIndex], a[right] )
(11) index ∈ N, index ← left
(12) for i from left to right – 1:
(13) if a[i] < pivot:
(14) swap( a[i], a[index] )
(15) index ← index + 1
(16) swap( a[index], a[right] )
(17) return index
Die Funktion quicksort selbst sollte relativ verständlich sein. Hier wird einfach nur durch den Aufruf der partition-Funktion ein Index in dem Datenfeld (durch Umsortierung, siehe unten) bestimmt, an welchem eine Unterteilung in eine linke “kleinere” und rechte “größere” Teilmenge erfolgen kann. Anschließend wird der Algorithmus rekursiv auf die beiden Teilfelder (beide exklusive des bestimmten Elementes) angewendet; das Abbruchkriterium in Zeile (2) besagt einfach, dass der Algorithmus dann nicht weiter in die Rekursion geht, wenn das zu sortierende Teilfeld nur noch die Größe 1 hat (also bereits sortiert ist).
Die eigentliche Magie von Quicksort geschieht in der partition-Funktion. Grob gesagt passiert hier folgendes: zuerst wird in Zeile (8) und (9) durch die Funktion choose ein Pivot-Element ausgewählt (siehe dazu unten); im Anschluss wird in Zeile (10) das Pivot-Element vorübergehend ans rechte Ende des Feldes geschoben. In den Zeilen (12) bis (15) wird durch das Feld von links nach rechts iteriert (mit Ausnahme des Pivot-Elements ganz rechts) und der in Zeile (11) initialisierte Index immer dann erhöht, wenn im Feld ein Element kleiner als das Pivot-Element gefunden wird; der Index markiert dabei die Stelle im Feld, bis zu der alle Elemente kleiner als das Pivot sind. Durch die Vertauschung in Zeile (14) wird sichergestellt, dass alle Element links des Indexes diese Bedingung erfüllen. Im Anschluss wird in Zeile (16) das temporär nach rechts geschobene Pivot-Element an die Stelle des Indexes kopiert, so dass die eben genannte Bedingung tatsächlich gilt und alle Elemente links des Pivot-Elements kleiner als das Element selber sind; schließlich wird in Zeile (17) der bestimmte Index zur weiteren Verwendung zurückgegeben.
Ein kleines Beispiel zur Verdeutlichung; nehmen wir an, wir haben das folgende (Teil-)Feld zum Sortieren:
Durch die Funktion choose wird nun zum Beispiel die 4 als Pivot-Element gewählt (markiert durch ein kleines p):
p
Als erstes wird das Pivot nun ganz nach rechts gesetzt, so dass sich folgendes Bild ergibt:
p
Nun beginnt der eigentliche Algorithmus; das Feld wird von links nach rechts durchlaufen (markiert durch die Laufvariable i), wobei der Index (markiert durch ^) immer dann verschoben wird, wenn ein Element kleiner als das Pivot-Element angetroffen wird; gleichzeitig wird in einem solchen Fall das gefundene Element mit dem Element an der Index-Position vertauscht wird (zu sehen in der 5. Zeile):
î p
î p
î p
^ i p
^ i/p
Als Endzustand ergibt sich also das folgende Umsortierte Feld, in welchem alle Elemente links des Pivot-Elements kleiner, alle rechts davon größer als das Pivot-Element selber sind. Die zurückgegebene Index-Position entspricht hier der Position der 4:
^
Nun würde man den Quicksort-Algorithmus rekursiv auf das linke und rechte Teilfeld anwenden (wobei beim rechten Teilfeld, bestehend aus der 5, keine weitere Sortierung nötig ist) und so Stück für Stück das gesamte Feld sortieren. Die Wahl des Pivot-Indexes kann übrigens nach unterschiedlichen Kriterien erfolgen; so kann zum Beispiel immer das Element ganz links oder rechts im Feld gewählt werden (wenngleich sich diese Wahl als ungünstig herausgestellt hat), es kann ein zufälliges Element gewählt werden oder ein Element, von dem erwartet werden kann, dass es ungefähr in der Mitte des Feldes zum Liegen kommt – letzteres wäre die beste Wahl für einen möglichst effizienten Algorithmus.
Die hier beschriebene Umsetzung des Quicksort-Algorithmus ist übrigens nur eine von vielen Varianten; die Bestimmung der Index-Position mit den dazu nötigen Vertauschungen kann auf unterschiedlichste Art und Weise erfolgen. In jedem Fall ist der Algorithmus aber sehr effizient und wird heutzutage als Standard-Sortieralgorithmus in vielen Programmen eingesetzt.
Und noch eine abschließende Information: Quicksort ist in der hier vorgestellten Implementierung ein sogenannter in-place-Algorithmus; derartige Algorithmen führen den Hauptteil ihrer Operationen auf den Eingabedaten selbst durch, benötigen also keinen zusätzlichen Speicherplatz zur Abarbeitung. Demgegenüber stehen die out-of-place-Algorithmen, welche folgerichtig zusätzlichen Speicherplatz benötigen (für die Interessierten: von Quicksort existiert auch eine out-of-place-Variante, welche mit Hilfe von Listen umgesetzt werden kann).
Kommentare (8)