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).
Kommentare (8)