04 – Merge-Sort und Quick-Sort

 

Bereits im letzten Kapitel haben wir den Rechenaufwand von Selection-Sort besprochen.
Dieser ergibt sich aus den ca. n2 / 2 Vergleichen und den n-1 Vertauschungen, die Laufzeit ist daher:

T\left( n \right) = \frac{{n^2 }} {2}+\left( {n-1} \right) = O\left( {n^2 } \right)

Denn:

T\left( n \right) \leq C \cdot n^2

Beispiel:

n = 1 \to T\left( n \right) = \frac{1} {2} < 1 \cdot n = 1

n = 2 \to T\left( n \right) = 2 < 2 \cdot n = 4

u.s.w.

Wir wollen nun ein besseres Verfahren zum Sortieren von Datensätzen finden.

Mergesort

Das Prinzip von Quicksort ist: “Teile und herrsche” (lat. “Divide et impera”)
Es bezeichnet das folgende Vorgehen:
Die große Aufgabe wird in mehrere Teilaufgaben, die jeweils kleiner und leichter zu lösen sind, zerlegt. Anschließend werden die Lösungen der Teilaufgaben verwendet, um die Gesamtlösung zu finden. Das Prinzip kann auch mehrfach angewendet werden, so dass immer kleinere Teilaufgaben entstehen, deren Lösungen dann kombiniert werden.

Beispiel:
Sortieren einer Menge mit n Elementen:

  • Bilde zwei Teilmengen von jeweils n/2 Einträgen
  • Sortiere diese mit Selection Sort (Aufwand: n2 / 4)
  • Kombiniere die beiden sortierten Teile (Aufwand: n / 2)
  • Der letzte Schritt erfolgt im Reißverschlussverfahren (englisch: to merge), bis wieder eine sortierte Gesamtliste erreicht ist.

    Durch die Zweiteilung der Liste spart man allerdings in Bezug auf die Rechenzeit nur am konstanten Faktor. Wir suchen daher weiter nach einem noch besseren Verfahren.

    Quicksort

    Eines der besten bekannte Sortierverfahren ist Quicksort. Es beruht auf dem Verfahren Mergesort, geht aber noch einen Schritt weiter mit dem Prinzip “teile und herrsche”.
    Statt die Liste einfach in der Mitte in zwei gleichgroße Teile zu zerlegen, wird das folgende Verfahren benutzt:

    unsortierte Startliste (gleiche wie bei Selection Sort):

    Im ersten Schritt wird ein Pivotelement gewählt. Hierfür gibt es verschiedene Verfahren, auf die später genauer eingegangen wird, wir wählen hier einfach das letzte Element:

    Nun wird die Liste durchgegangen und jedes Element, das größer ist als das Pivotelement, wird rechts von diesem in die Liste geschrieben:

    Anschließend wird die Liste an der aktuellen Stelle des Pivots getrennt in zwei neue Listen:

    Im zweiten Schritt wird für jede der zwei Teillisten erneut der Sortieralgorithmus Quicksort aufgerufen. Nach dem zweiten Schritt ist die Liste sortiert:

    Dieses erneute Aufrufen der Funktion aus der Funktion heraus nennt man “Rekursion”. Mit “Rekursionstiefe” bezeichnet man die Anzahl der Ebenen, in denen der Algorithmus aufgerufen wird. Im Beispiel ist die Rekursionstiere gleich 2, da die Funktion nach ihrem ersten Aufruf nur eine Ebene tiefer gehen muss, bis die Liste fertig sortiert ist.

    Wenn man über die Laufzeit dieses Sortierverfahrens nachdenkt, erhält man verschiedene Möglichkeiten, die davon abhängen, wie “gut” die Liste in jedem Schritt geteilt wird.
    Im Optimalfall wird sie in jedem Schritt jeweils in zwei gleich große Teile geteilt.
    Die Rekursionstiefe ist dann log(n). Da für jede Stufe O(n) Rechenoperationen benötigt werden, ergibt sich eine Laufzeit von O(n log(n)), was viel besser ist als bei Selection Sort. Wenn allerdings in jedem Schritt nur ein Element von der Liste abgespalten wird, steigt die Rekursionstiefe auf n, somit der Gesamtaufwand auf O(n2). Dies ist der Fall, wenn die Liste schon vor dem Aufruf der Sortierfunktion fertig sortiert ist.

    Da dies ein kritischer Faktor ist, versucht man sicherzustellen, dass Quicksort sich immer für ein “optimales” Pivotelement entscheidet. Hierfür gibt es verschiedene Ansätze:

    • Bisheriger Ansatz: Wir benutzen immer das letzte Element als Pivot. Nachteil: Wenn die Liste bereits sortiert ist, ergibt sich so ein hoher Rechenaufwand.
    • Alternative: Wir benutzen den bisherigen Ansatz, sortieren die Liste aber vor dem Aufruf von Quicksort zufällig. Dadurch wird sichergestellt, dass die Liste nicht vorsortiert ist. Nachteil: Es können sich trotzdem ungünstige Konstellationen ergeben, wo diese Aufteilung nicht optimal funktioniert.
    • andere Lösung: Wir vergleichen das erste Element (A[links], das letzte (A[rechts] und das mittlere (A[(l+r) / 2] Element der Liste und wählen als Pivot das mit dem mittleren Wert.

    Nun setzen wir den Algorithmus in Pseudocode um.

    Zunächst die Grundstruktur wie oben beschrieben:

    quicksort(A[], links, rechts)
    {
    	if l < r
    	{
    		p = partition(A[], links, rechts)
    		quicksort(A[], links, p-1)
    		quicksort(A[], p+1, rechts)
    	}
    }
    

    Als Parameter übernimmt der Quicksort Algorithmus die Liste A, die linke Grenze und die rechte Grenze. Im ersten Schritt ist die linke Grenze = 0, die rechte Grenze = n-1. Wie wir gleich feststellen werden, ist die linke Grenze aber nicht einfach in jedem Schritt durch 0 zu ersetzen, die rechte auch nicht durch n-1.
    In der Funktion wird als erstes überprüft, ob l kleiner ist als r. Ist dies nicht der Fall, so ist die linke Grenze genauso weit oder sogar noch weiter rechts als die rechte. Der Algorithmus tut also nur etwas, wenn die linke Grenze auch links ist. (ist l = r, so ist das übergebene Intervall der Liste nur ein Element groß).
    Nun muss das Pivot bestimmt werden. Die kleineren Elemente müssen nach links, die größeren nach rechts sortiert werden. Wie dies geschieht, sehen wir im Anschluss in der Funktion partition().
    Ist dies geklärt, wird in der Funktion Quicksort erneut die Funktion Quicksort aufgerufen, allerdings zwei Mal mit anderen Grenzen:
    Der erste Aufruf lässt das Intervall vom aktuellen “links” bis zum Element vor dem Pivot sortieren, der zweite Aufruf lässt das Intervall ab dem Element hinter dem Pivot bis zum aktuellen “rechts” sortieren.

    Nun zur Hauptfunktion, der Funktion partition:

    partition(A[], links, rechts)
    {
    	pivot = A[rechts]
    	i = links
    	// Starte mit j links vom Pivotelement
    	j = rechts-1
    
    	wiederhole
    	{
    		// Suche von links ein Element größer als das Pivotelement
    		wiederhole solange A[i] <= pivot und i < rechts
    			i = i+1  
    
    		// Suche von rechts ein Element kleiner als das Pivotelement
    		wiederhole solange A[j] >= pivot und j > links
    			j = j-1 
    
    		falls i < j dann tausche A[i] mit A[j]
    	} solange i < j // solange i an j nicht vorbeigelaufen ist 
    
    	// Tausche Pivotelement (A[rechts]) mit neuer Position (A[i])
    	falls A[i] > pivot
    		tausche A[i] mit A[rechts] 
    
    	// gib die Position des Pivotelements zurück
    	antworte i
    }