Effizientere Sortierverfahren

Wir lernen nun klassische rekursive Sortierverfahren kennen. Auch die Implementierung von Insertion Sort kann mit Hilfe eines rekursiven Aufrufs implementiert werden, nach dem das letzte Element an der richtigen Stelle eingefügt wird. Der Schlüssel zur Effizienz der folgenden Sortierverfahren ist es jedoch, Teil-Listen mit mehreren rekursiven Aufrufen zu sortieren.

Quick Sort

Die Idee von Quick Sort ist es, eine Partitionierung genannte grobe Vorsortierung durch Anwendung rekursiver Aufrufe zu vervollständigen. Die Partitionierung stellt dabei sicher, dass sich alle Elemente, die kleiner sind als ein gegebenes, im vorderen Teil und alle größeren im hinteren Teil befinden. Anschließend werden der vordere und der hintere Teil getrennt voneinander rekursiv sortiert.

Um verschiedene Teile getrennt voneinander sortieren zu können, übergeben wir als zusätzliche Parameter die Grenzen des zu sortierenden Bereiches, die mit den Grenzen der Liste initialisiert werden:

def quick_sort(a):
    qsort(a, 0, len(a)-1)

Die rekursive Prozedur qsort implementiert das beschriebene Sortierverfahren:

def qsort(a, l, r):
    if l < r:
        m = partition(a, l, r)
        qsort(a, l, m-1)
        qsort(a, m+1, r)

Falls der zu sortierende Bereich mehr als ein Element enthält, wird er zunächst in zwei Bereiche mit der Grenze m partitioniert, die danach rekursiv sortiert werden. Die Prozedur partition ist eine alte Bekannte in neuem Gewand. Wir haben früher bereits ein Programm gesehen, dass eine Liste auf die beschriebene Weise partitioniert. Die folgende Prozedur verallgemeinert dieses Programm so, dass die Grenzen des zu bearbeitenden Bereiches angegeben werden können:

def partition(a, l, r):
    m = l
    for i in range(l, r):
        if a[i+1] < a[l]:
            m = m + 1
            swap(a, i+1, m)
    swap(a, l, m)
    return m

Das Element an Position l dient hier als sogenanntes Partitionselement oder Pivot-Element. Die anderen Elemente des Bereiches werden so umsortiert, dass diejenigen Elemente, die kleiner sind als das Partitionselement vor allen stehen, die größer oder gleich sind. Am Ende steht das Partitionselement an Position m und diese Position wird zurückgegeben.

Die folgende Programmtabelle dokumentiert die Ausführung von partition für die Parameter a = [1,2,3,6,7,4,8,5], l = 3 und r = 7.

Partitioniert wird also die Teilliste [6,7,4,8,5] um das Partitionselement 6.

Zur Evaluation der Effizienz von Quick Sort rufen wir es mit zufälligen Listen unterschiedlicher Größe auf. Dabei ergeben sich auf meinem Rechner die folgenden Laufzeiten:

1000: 
0.002292633056640625
2000: 
0.0047588348388671875
4000: 
0.010391712188720703
8000: 
0.022547483444213867
16000: 
0.04721498489379883
32000: 
0.10293197631835938
64000: 
0.23071861267089844
128000: 
0.48602795600891113
256000: 
1.0562872886657715
512000: 
2.241218328475952

Wir können beobachten, dass sich die Laufzeit bei Verdoppelung der Eingabegröße meist ein wenig mehr als verdoppelt. Die Laufzeit erscheint also fast linear, aber nicht ganz.

Intuitiv können wir uns den Aufwand von Quick Sort verdeutlichen, indem wir den Aufwand für die einzelnen Aufrufe von partition zusammenfassen. Der erste Aufruf durchläuft die Eingabe-Liste einmal komplett um es zu partitionieren. Dann folgen zwei rekursive Aufrufe von qsort, deren partition-Aufrufe die Liste zusammengenommen ebenfalls komplett durchlaufen. Je nach Größe der dabei sortierten Bereiche folgen wieder rekursive Aufrufe, die zusammengenommen das ganze Feld durchlaufen. Um den gesamten Aufwand abzuschätzen ist also die Rekursionstiefe entscheidend, denn sie entscheidet, wie oft die Eingabe-Liste durchlaufen wird.

Im besten Fall wird das Feld vor jedem Rekursionsschritt in gleich große Hälften partitioniert und die Rekursionstiefe ist der Logarithmus der Größe der Eingabe-Liste. Dabei ergibt sich also eine Laufzeit in \(\mathcal{O}(n \cdot \log_2(n)\). Diese Laufzeit ergibt sich auch gemittelt über alle Eingaben also im Durchschnittsfall und erklärt damit unsere experimentellen Beobachtungen.

Im schlechtesten Fall hat die eine Hälfte der Partition die Größe 1 und die andere enthält alle weiteren Elemente. Dieser Fall tritt ein, wenn das Feld sortiert oder umgekehrt sortiert ist. In diesem Fall ist die Rekursionstiefe linear in der Eingabegröße, die Laufzeit also in \(\mathcal{O}(n^2)\).

Die folgende Tabelle fasst die Laufzeiten der bisher diskutierten Sortierverfahren zusammen.

Quick Sort erreicht also gegenüber den bisherigen Verfahren eine wesentliche Verbesserung im Average Case auf Kosten einer unwesentlichen Verschlechterung im Best Case gegenüber Insertion Sort.

Es gibt Sortierverfahren, die die Laufzeit auch im Worst Case verbessern. Im Rahmen der Übung haben Sie die Möglichkeit sich mit ihnen zu befassen.