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).

1 / 2 / Auf einer Seite lesen

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.