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:

(1)  sum: n ∈ N → N:
(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:

(1)  sum: n ∈ N → N:
(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):

(1)  quicksort: a ∈ Nn × left, right ∈ N → ():
(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 ∈ NN:
(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:

1  4  5  2  3

Durch die Funktion choose wird nun zum Beispiel die 4 als Pivot-Element gewählt (markiert durch ein kleines p):

1  4  5  2  3
p

Als erstes wird das Pivot nun ganz nach rechts gesetzt, so dass sich folgendes Bild ergibt:

1  3  5  2  4
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):

1  3  5  2  4
î           p
1  3  5  2  4
î        p
1  3  5  2  4
î     p
1  3  5  2  4
^  i  p
1  3  2  5  4
^  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:

1  3  2  4  5
^

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)

  1. #1 m
    Oktober 24, 2011

    in place bis auf O(log n) index-Variablen (im Beispiel sogar O(n) worst case)</pingelig>

  2. #2 rolak
    Oktober 25, 2011

    moin m, so weit ich weiß, gibt es eine engere und eine weitere Auffassung von in/out-of-place, letztere bezieht sich auf das direkte Manipulieren bzw Überschreiben des Inputs, erstere zusätzlich auf die Problemunabhängigkeit des zusätzlich benötigten Speicherplatzes.

  3. #3 m
    Oktober 26, 2011

    Mist, definitionen. Allerdings scheint mir die weitere Auffassung etwas beliebig; damit kann man wohl jeden Sortieralgorithmus in-place implementieren, in dem man ein Feld/eine Liste mit Indices mit einem beliebigen Verfahren sortiert, and dann das Eingabefeld in die so erhaltene Reihenfolge bringt.

  4. #4 Marcus Frenkel
    Oktober 26, 2011

    @m
    Der ursprüngliche Einwand war korrekt, rolaks Korrektur aber auch. In-Place-Algorithmen beziehen sich in der engeren Bedeutung darauf, dass die Eingabe direkt manipuliert wird. In der allgemeinen Auffassung in Bezug auf den tatsächlich benötigten Speicherplatz ist Quicksort in der Tat kein in-place-Algorithmus, da durch die Rekursion viel Speicher benötigt wird. An der Stelle ist die Begrifflichkeit leider ein wenig schwammig, da stimme ich zu.

  5. #5 michael
    Oktober 27, 2011

    > da durch die Rekursion viel Speicher benötigt wird.

    Die Rekursionstiefe ist aber durch die Länge des Eingabevektor beschränkt, und damit ist der benötigte Speicherplatz durch Konstante * Länge des Eingabevektor beschränkt.

    Die Rekursion kann man auch mit Hilfe einer Queue z.B. eliminieren, wenn es denn sein muss.

  6. #6 Marcus Frenkel
    Oktober 27, 2011

    @michael
    Prinzipiell richtig, aber da der benötigte Speicherplatz von der Länge des Eingabevektors und damit von der Problemgröße abhängt, hat man eben doch keinen absolut reinen in-place-Algorithmus in der Betrachtung auf den absolut benötigten Speicherplatz (sondern nur, wenn man allein die zu sortierenden Daten betrachtet).
    Die Queue hilft diesbezüglich auch nicht weiter, da deren Länge natürlich genauso von der Eingabe abhängt.

  7. #7 sebix
    Oktober 29, 2011

    Ich hab auch noch was zum Meckern 😀
    “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.”
    Da der Quicksort auf O(n²) ausarten kann, ist er nicht in geschwindigkeits-relevanten Programmen verwendbar, bspw in Mail-Servern. Dort wird dann eine Mischung aus Quicksort und Mergesort verwendet.
    In der Standard-Template-Library STL (C++) wurde früher Quicksort verwendet, inzwischen wechselte man aber zum sog. Introsort (siehe dazu die SGI-Doku)

  8. #8 Marcus Frenkel
    Oktober 29, 2011

    @sebix
    Einwand teilweise angenommen. 😉
    Das Quicksort nicht der Weisheit letzter Schluss ist, ist absolut korrekt – habe ich aber auch gar nicht behauptet. Nur, dass es ein ziemlich häufig verwendeter Algorithmus ist, was vermutlich auch an der einfachen Implementierung liegen dürfte.
    Sobald es ernsthaft auf die Geschwindigkeit angeht und um wirklich große Datenmengen geht, kommt man um spezialisierte Algorithmen vermutlich ohnehin nicht mehr herum, die etwas genauer an das zu lösende Problem angepasst sind. Die ganzen X-Sort-Algorithmen sind ja mehr oder weniger Standardlösungen, die ohne das Wissen um die Problemdomäne benutzt werden können (und da liegt ihr Charme).

    Dass die STL aber gar kein Quicksort mehr verwendet, ist an mir vorbeigegangen. Vielen Dank für den Hinweis.