FLBK-Wiki

Quicksort: Unterschied zwischen den Versionen

← Zum vorherigen Versionsunterschied
Flbkwikiadmin (Diskussion | Beiträge)
Bürokraten, Oberflächenadministratoren, Administratoren
2.195 Bearbeitungen
VisuellWikitext
 
(9 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
== Einführung ==
== Einführung ==
[[Datei:Rekursive Baumstruktur.jpg|mini]]
[[Datei:Rekursive Baumstruktur.jpg|mini|Rekursive Aufteilung beim Quicksort]]
Ein oft eingesetzter [[Sortieren|Sortier]]-Algorithmus ist der Quicksort. Der Quicksort funktioniert nach dem Prinzip »teile und herrsche«, was mit Hilfe der [[Rekursion]] realisiert wird. Die zu sortierenden [[Daten]] werden immer in zwei Teile zerlegt ("Teile") und wieder sortiert ("Herrsche")). Diese zwei Teile werden wiederum jeweils in zwei Teile zerlegt und sortiert usw., bis die Daten sortiert sind. Die [[Rekursion]] beendet sich, wenn das Teilstück aus nur noch einem Element besteht (http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm#mj035bded10a26be556df779f234784e89).
Ein in der Praxis oft eingesetzter und sehr effizienter [[Sortieren|Sortieralgorithmus]] ist der '''Quicksort''' (englisch für „schnelles Sortieren“). Er funktioniert nach dem Prinzip '''„Teile und herrsche“''' (Divide and Conquer), welches in der Programmierung meist mithilfe von [[Rekursion]] realisiert wird.  


Die Zerlegung in zwei Teile erfolgt anhand eines sogenannten Pivot-Elementes. Ein Element der Liste wird als Pivot Element ausgewählt und dann werden alle weiteren Elemente der zu sortierenden Liste mit diesem Element verglichen. Die zu sortierende Liste wird in zwei Bereiche unterteilt. Alle Elemente die kleiner sind als das Pivot-Element werden links von dem Pivot-Element einsortiert. Alle Elemente die größer sind, werden rechts von Pivot-Element abgelegt.
Die Grundidee ist einfach: Die zu sortierende Datenmenge wird in zwei kleinere Teillisten zerlegt ("Teile") und diese werden anschließend separat sortiert ("Herrsche"). Diese Teillisten werden wiederum in noch kleinere Teillisten zerlegt, bis eine Liste nur noch aus einem einzigen Element besteht. Eine Liste mit nur einem Element ist naturgemäß immer sortiert – an diesem Punkt endet die [[Rekursion]] [http://openbook.galileocomputing.de/c_von_a_bis_z/022_c_algorithmen_003.htm (vgl. Galileo Computing)].


Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich dem Pivot-Element und somit auch kleiner oder gleich den Elementen der rechten Liste. Die Elemente der linken und rechten Liste sind je Liste noch unsortiert.
=== Wie funktioniert die Zerlegung (Partitionierung)? ===
Die Zerlegung der Liste erfolgt anhand eines sogenannten '''Pivot-Elements''' (Dreh- und Angelpunkt).  
# Ein beliebiges Element der Liste wird als Pivot ausgewählt.
# Alle anderen Elemente der Liste werden mit diesem Pivot verglichen.
# Die Liste wird in zwei Bereiche unterteilt:
#* '''Linke Teilliste:''' Alle Elemente, die kleiner (oder gleich) dem Pivot sind.
#* '''Rechte Teilliste:''' Alle Elemente, die größer als das Pivot sind.


Anschließend muss man noch jede Teilliste in sich sortieren, um die Sortierung zu vollenden. Dazu wird der Quicksort-Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgeführt. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so fort.
Nach diesem Schritt steht das Pivot-Element bereits an seiner endgültigen, korrekten Position in der Liste. Die Elemente in der linken und rechten Teilliste sind zwar untereinander noch unsortiert, aber es ist garantiert, dass alle Elemente links vom Pivot kleiner sind als alle Elemente rechts davon.


Die Teillisten sind immer Abschnitte auf der ursprünglichen Liste, so dass kein zusätzlicher Speicher benötigt wird.  
Anschließend ruft sich der Quicksort-Algorithmus selbst auf (Rekursion), um die linke und die rechte Teilliste nach exakt demselben Muster weiter zu sortieren. Ein großer Vorteil dieses Verfahrens: Die Teillisten sind immer Abschnitte der ursprünglichen Liste. Es wird also (abgesehen vom Speicher für die Rekursionsaufrufe) kein zusätzlicher Speicherplatz für neue Listen benötigt (In-Place-Sortierung).


== Beispiel ==
== Beispiel ==
Als Beispiel betrachten wir eine Liste mit Zahlen. Wir wählen immer das erste Element als Pivot-Element. Zu Beginn ist die Zahl 7 zufällig das Pivot-Element.
Als Beispiel betrachten wir eine unsortierte Liste mit Zahlen. Der Einfachheit halber wählen wir in diesem Beispiel immer das '''erste Element''' als Pivot-Element. Zu Beginn ist die Zahl 7 also unser Pivot.


7 <span style="color:red">10 8</span> <span style="color:blue">6</span> <span style="color:red">11</span> <span style="color:blue">4</span> <span style="color:red">9</span> <span style="color:blue">3 1 5 2</span> <span style="color:red">12</span>
7 <span style="color:red">10 8</span> <span style="color:blue">6</span> <span style="color:red">11</span> <span style="color:blue">4</span> <span style="color:red">9</span> <span style="color:blue">3 1 5 2</span> <span style="color:red">12</span>


Die Zahlen, die kleiner als das Pivot-Element 7 sind, wurden blau markiert. Die Zahlen größer 7 haben sind rot markiert. Als ersten Schritt ändert QuickSort die Liste folgendermaßen:
Die Zahlen, die kleiner als das Pivot-Element 7 sind, wurden blau markiert. Die Zahlen, die größer als 7 sind, wurden rot markiert. Nach dem ersten Partitionierungsschritt hat QuickSort die Liste folgendermaßen umgeordnet:


3 <span style="color:blue">2</span> <span style="color:red">5 6</span> 1 <span style="color:red">4</span> 7 9 11 8 10 12
<span style="color:blue">3 2 5 6 1 4</span> '''7''' <span style="color:red">9 11 8 10 12</span>


Nun sind alle Zahlen, welche kleiner sind als 7, links von ihr. Alle Zahlen welche größer sind als die 7, stehen rechts. Die Reihenfolge der Zahlen in den Teillisten ist hier willkürlich und hängt ab von der jeweiligen Implementierung. Entscheidend ist, dass alle Zahlen die kleiner sind als 7 links stehen und alle Zahlen die größer sind als 7 rechts.
Nun stehen alle Zahlen, die kleiner sind als 7, links von ihr. Alle Zahlen, die größer sind, stehen rechts. Die Reihenfolge der Zahlen innerhalb der blauen und roten Teillisten ist hier noch willkürlich und hängt von der genauen Programmierung ab. Entscheidend ist: '''Die 7 hat nun ihre endgültige, korrekte Position gefunden.'''


Als nächstes wird der Teil links von der 7 wieder per QuickSort sortiert. Als Pivot wird die Zahl 3 gewählt. Die Zahlen die kleiner sind als 3 werden wieder blau markiert. Alle Zahlen größer 3 sind rot. Die Zahl 7 und die größeren Zahlen betrachten wir im Moment nicht, deshalb sind sie gelb hinterlegt:
Als Nächstes wird die linke (blaue) Teilliste per QuickSort sortiert. Als neues Pivot wählen wir wieder die erste Zahl des Bereichs, die 3. Die Zahlen, die kleiner sind als 3, werden wieder blau markiert, die größeren rot. Die bereits einsortierte 7 und die rechte Teilliste ignorieren wir für den Moment (grau hinterlegt):


3 <span style="color:blue">2</span> <span style="color:red">5 6</span> <span style="color:blue">1</span> <span style="color:red">4</span> 7 9 11 8 10 12
'''3''' <span style="color:blue">2</span> <span style="color:red">5 6</span> <span style="color:blue">1</span> <span style="color:red">4</span> <span style="color:gray">7 9 11 8 10 12</span>


Der Algorithmus bringt die blauen und die roten Zahlen wieder in die richtige Ordnung. Man erhält dann das Folgende:
Der Algorithmus sortiert die Elemente relativ zur 3 um:


<span style="color:blue">1 2</span> 3 <span style="color:red">6 5 4</span> 7 9 11 8 10 12
<span style="color:blue">1 2</span> '''3''' <span style="color:red">6 5 4</span> <span style="color:gray">7 9 11 8 10 12</span>


Das wird fortgesetzt bis der linke Teil des Arrays sortiert ist. Das sieht dann wie folgt aus:
Dieser Prozess wird fortgesetzt (erst die 1 und 2, dann die 6, 5 und 4), bis der gesamte linke Teil des Arrays vollständig sortiert ist. Das Ergebnis sieht dann so aus:


  '''''1 2 3 4 5 6''''' 7 9 11 8 10 12
''1 2 3 4 5 6'' '''7''' <span style="color:gray">9 11 8 10 12</span>


Nun wird rechts von der 7 sortiert. Wieder wird ein Pivot gewählt, hier die 9, und die kleineren und größeren Zahlen auf die jeweils richtige Seite gebracht.
Anschließend wird die Teilliste rechts von der 7 nach demselben Prinzip sortiert. Wieder wird ein Pivot gewählt (hier die 9), und die kleineren und größeren Zahlen werden auf die jeweils richtige Seite gebracht, bis das gesamte Array sortiert ist.


Der grundsätzlichen Algorithmus lässt mit PseudoCode wie folgt beschreiben:
== Pseudocode ==
Der folgende Pseudocode illustriert die Arbeitsweise des [[Algorithmus]]. Bei jedem Aufruf von <code>quicksort(...)</code> gibt <code>links</code> den Index des ersten Elements in der Teilliste an und <code>rechts</code> den des letzten. Beim ersten Aufruf (oberste Rekursionsebene) ist <code>links = 0</code> und <code>rechts = n-1</code>.


== Pseudocode ==
<syntaxhighlight lang="text">
Der folgende Pseudocode illustriert die Arbeitsweise des [[Algorithmus]]. Bei jedem Aufruf von quicksort(...) gibt links den Index des ersten Elements in der Teilliste an und rechts den des letzten. Beim ersten Aufruf (oberste Rekursionsebene) ist links = 0 und rechts = n-1. Die übergebene Liste wird dabei [[Rekursion|rekursiv]] immer weiter geteilt, bis sie nur noch einen Wert enthält.
<syntaxhighlight>
funktion quicksort(links, rechts)  
funktion quicksort(links, rechts)  
     falls links < rechts dann  
     falls links < rechts dann  
        // teile() ordnet das Array um und liefert die finale Position des Pivots
         teiler := teile(links, rechts)  
         teiler := teile(links, rechts)  
       
        // Rekursiver Aufruf für die linke Teilliste
         quicksort(links, teiler - 1)  
         quicksort(links, teiler - 1)  
       
        // Rekursiver Aufruf für die rechte Teilliste
         quicksort(teiler + 1, rechts)  
         quicksort(teiler + 1, rechts)  
     ende
     ende
ende
ende
</syntaxhighlight>
</syntaxhighlight>
== Wahl des Pivot-Elements ==
== Wahl des Pivot-Elements ==
Die Wahl des Pivotelements ist wichtig. Die schlechteste Wahl des Pivots ist das Element, welches ganz am linken oder ganz am rechten Rand des zu sortierenden Intervalls endet. Mit linkem oder rechten Element ist nicht das Element gemeint, welches sich in der unsortierten Liste ganz Links (im Beispiel die 7) oder rechts befindet, sondern das kleinste (im Beispiel die 1) bzw. das größte Element (im Beispiel die 12). Der QuickSort ist dann am Effizientesten, wenn man ein Pivot-Element wählt, welches am Schluss genau in der Mitte zu liegen kommt (im Beispiel die 6 oder die 7). Leider ist dieses Element nicht ganz einfach zu finden.
Die Effizienz von Quicksort steht und fällt mit der Wahl des Pivot-Elements.  


Man sollte deshalb nicht immer wie im Beispiel das erste Element als Pivot wählen. Dies ist zwar leicht zu implementieren, allerdings führt dies zu einem langsamen "QuickSort", falls  das Array bereits sortiert ist, oder nahezu sortiert ist.
* '''Schlechteste Wahl:''' Das Pivot-Element ist zufällig immer das kleinste oder größte Element der Teilliste. Dann wird die Liste extrem ungleichmäßig geteilt (eine Liste mit 0 Elementen, eine mit <math>n-1</math> Elementen).
* '''Beste Wahl:''' Das Pivot-Element ist genau der [[Median]] (der Wert, der exakt in der Mitte der sortierten Liste stehen würde). Die Liste wird in zwei exakt gleich große Hälften geteilt. Da der Median in unsortierten Daten aber aufwendig zu suchen ist, behilft man sich mit Tricks.


Als Kompromiss wird oft ein zufälliges Element als Pivot-Element genommen. Noch besser kann es sein, von drei zufällig gewählten Elementen jeweils das mittlere zu nehmen.
'''Warum das erste Element oft eine schlechte Wahl ist:'''
Wenn man immer stur das erste Element als Pivot wählt (wie in unserem Beispiel) und die Eingabeliste ist bereits (oder fast) fertig sortiert, trifft automatisch immer der oben beschriebene schlechteste Fall ein. Der Algorithmus wird dadurch extrem langsam.
 
'''Lösungsansätze für die Praxis:'''
# '''Randomisierung:''' Man wählt ein zufälliges Element aus dem Intervall als Pivot.
# '''Median-of-Three:''' Man betrachtet das erste, das mittlere und das letzte Element der Teilliste und wählt von diesen dreien den mittleren Wert als Pivot. Dies schützt sehr gut vor bereits vorsortierten Listen.


== Java Implementierung ==
== Java Implementierung ==
Bisher wurde die allgemeine Funktionsweise des Quicksorts beschrieben. Am Besten lassen sich komplexe [[Algorithmus|Algorithmen]] nachvollziehen, wenn Sie anhand einer Implementierung mit Hilfe eines [[Debugger|Debuggers]] analysiert werden.  Mit Hilfe des Quicksorts können beliebige Datenstrukturen sortiert werden. In der folgenden [[Java]] Implementierung wird ein [[Array]] bestehend aus Integern (kurz int) sortiert.
Bisher wurde die allgemeine Funktionsweise beschrieben. Am besten lassen sich komplexe [[Algorithmus|Algorithmen]] nachvollziehen, wenn man sie anhand einer Implementierung mit Hilfe eines [[Debugger|Debuggers]] analysiert. In der folgenden [[Java]]-Implementierung wird ein [[Array]] aus Ganzzahlen (<code>int</code>) sortiert.  
 
Zur Abwechslung wird in dieser Implementierung immer das '''letzte''' Element des aktuellen Bereichs (<code>array[rechts]</code>) als Pivot gewählt.
 
<syntaxhighlight lang="java">
<syntaxhighlight lang="java">
public void quickSort(int array[], int links, int rechts) {
public void quickSort(int array[], int links, int rechts) {
       if (links < rechts) {
       if (links < rechts) {
         int i = teile(array,links,rechts);
        // Teile das Array und finde die Position des Pivot-Elements
         quickSort(array,links,i-1);
         int i = teile(array, links, rechts);
         quickSort(array,i+1,rechts);
       
        // Sortiere den linken Teil
         quickSort(array, links, i - 1);
        // Sortiere den rechten Teil
         quickSort(array, i + 1, rechts);
       }
       }
  }
}


  public int teile(int array[], int links, int rechts) {
public int teile(int array[], int links, int rechts) {
       int pivot, i, j, help;
       int pivot, i, j, help;
       pivot = array[rechts];               
       pivot = array[rechts]; // Wir wählen das rechte Randelement als Pivot                
       i     = links;
       i = links;
       j     = rechts-1;
       j = rechts - 1;
       while(i<=j) {
     
      // Von links und rechts zur Mitte laufen, bis sich i und j kreuzen
       while (i <= j) {
        // Suche von links ein Element, das größer als das Pivot ist
         if (array[i] > pivot) {     
         if (array[i] > pivot) {     
             // tausche x[i] und x[j]
             // Tausche array[i] mit array[j], um es in den rechten Bereich zu bringen
             help = array[i];  
             help = array[i];  
             array[i] = array[j];  
             array[i] = array[j];  
             array[j] = help;                             
             array[j] = help;                             
 
             j--; // j einen Schritt weiter nach links schieben
             j--;
         } else {
         } else i++;          
            i++; // i war kleiner/gleich Pivot, ist also korrekt positioniert -> weiter nach rechts
        }         
       }
       }


       // tausche x[i] und x[rechts]
       // Das Pivot-Element an seine endgültige Position (i) tauschen
       help     = array[i];
       help = array[i];
       array[i]     = array[rechts];
       array[i] = array[rechts];
       array[rechts] = help;
       array[rechts] = help;
     
      // Rückgabe der finalen Position des Pivot-Elements
       return i;
       return i;
  }
}
</syntaxhighlight>
 
== Vorbereitung: Indikatorvariablen und die Harmonische Reihe ==
Bei komplexeren Algorithmen wie [[Quicksort]] reicht einfaches Zählen der Vergleiche oft nicht mehr aus. Hier arbeiten wir in der Laufzeitanalyse mit einem stochastischen Werkzeug: '''Indikatorvariablen''' und der '''Harmonischen Reihe'''. Um das Prinzip zu verinnerlichen, analysieren wir vorab einen simplen Code zur Maximumsuche:
 
<syntaxhighlight lang="java">
public int findMax(int[] A) {
    int max = A[0];
    for (int i = 1; i < A.length; i++) {
        if (A[i] > max) {
            max = A[i]; // Update-Operation
        }
    }
    return max;
}
</syntaxhighlight>
</syntaxhighlight>
Die Vergleiche in der <code>if</code>-Bedingung werden immer exakt <math>n-1</math> Mal ausgeführt. Aber wie oft wird die Variable <code>max</code> im Durchschnitt tatsächlich überschrieben (Update-Operation)?
Wir stellen uns vor, das Array enthält völlig zufällig gemischte Zahlen.
* '''Intuitiver Ansatz:'''
Das 1. Element ist automatisch das bisherige Maximum (Wahrscheinlichkeit: 1).
Damit das 2. Element ein neues Maximum ist, muss es größer als das erste sein. Die Chance dafür ist bei zufälliger Verteilung exakt 50% (<math>\frac{1}{2}</math>).
Damit das 3. Element ein neues Maximum ist, muss es das Größte der ersten drei Elemente sein. Die Chance dafür ist <math>\frac{1}{3}</math>.
* '''Mathematischer Ansatz (Indikatorvariablen):'''
Wir definieren einen „Schalter“ (die Indikatorvariable) <math>X_i</math>. Er ist <math>1</math>, wenn ein neues Maximum an Stelle <math>i</math> gefunden wird, sonst <math>0</math>. Die Wahrscheinlichkeit dafür ist <math>P(X_i = 1) = \frac{1}{i}</math>.
Um die durchschnittliche Gesamtzahl der Updates zu finden, addieren wir einfach diese Wahrscheinlichkeiten auf:
<math>E[X] = \sum_{i=1}^{n} \frac{1}{i} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \dots + \frac{1}{n}</math>
Diese spezielle Summe nennt man in der Mathematik die '''Harmonische Reihe''' (<math>H_n</math>). Sie wächst extrem langsam. Für große Zahlen <math>n</math> entspricht sie in etwa dem '''natürlichen Logarithmus''' (<math>\ln(n)</math>).
'''Erkenntnis für Quicksort:''' Obwohl das Array <math>n</math> Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft (<math>\mathcal{O}(\log n)</math>) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um im nächsten Abschnitt zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt.
== Laufzeitanalyse ==
=== Best-Case (Bester Fall) ===
[[Datei:Verzweigungsbaum Quicksort symetrisch.png|mini|Best-Case: Symmetrischer Baum]]
Der beste Fall liegt vor, wenn das Pivot-Element die Liste in jedem Rekursionsschritt exakt in der Mitte teilt. Die entstehenden Teillisten sind dann immer gleich groß.
[[Datei:SubArrays symetrisch Quicksort.png|mini|Halbierung der Arraygrößen]]
Wird die Anzahl der zu sortierenden Elemente <math>n</math> verdoppelt, kommt durch die fortlaufende Halbierung lediglich '''eine einzige neue Rekursionsebene''' (ein Baum-Level) hinzu. Dieses Wachstumsverhalten (Wie oft kann ich <math>n</math> durch 2 teilen, bis 1 übrig bleibt?) wird mathematisch durch den Logarithmus zur Basis 2 ausgedrückt: <math>\log_2(n)</math>.
{| class="wikitable" style="text-align:center"
|-
! Zu sortierende Elemente <math>n</math>
| style="color:green" | 4
| style="color:green" | 8
| style="color:green" | 16
| style="color:green" | 32
|-
! Als Zweierpotenz
| <math>\color{green}{2^2}</math>
| <math>\color{green}{2^3}</math>
| <math>\color{green}{2^4}</math>
| <math>\color{green}{2^5}</math>
|-
! Anzahl Rekursionsebenen <math>\log_2(n)</math>
| style="color:red" | 2
| style="color:red" | 3
| style="color:red" | 4
| style="color:red" | 5
|}
Wir haben also insgesamt <math>\log_2(n)</math> Ebenen. Nun müssen wir noch den Aufwand pro Ebene bestimmen: Obwohl die einzelnen Teillisten nach unten hin immer kürzer werden, verdoppelt sich gleichzeitig ihre Anzahl. Auf '''jeder einzelnen Ebene''' müssen daher in der Summe über alle Teillisten hinweg wieder (nahezu) <math>n</math> Elemente betrachtet und mit den jeweiligen Pivots verglichen werden.
Wir multiplizieren also die Arbeit pro Ebene (<math>n</math> Vergleiche) mit der Anzahl der Ebenen (<math>\log_2(n)</math>).
'''Fazit Best-Case:''' Die Laufzeit beträgt <math>\mathcal{O}(n \log n)</math>.
=== Average-Case (Durchschnittlicher Fall) ===
In der Praxis haben wir fast nie den perfekten Best-Case, aber zum Glück auch extrem selten den absoluten Worst-Case. Meistens teilt das Pivot die Liste in ungleiche, aber moderate Verhältnisse (z. B. 30:70 oder 60:40). Auch bei solchen ungleichen Teilungen wächst die Tiefe des Baumes weiterhin nur logarithmisch.
Um den Average-Case mathematisch exakt zu beweisen, greifen wir auf Stochastik und unser Vorwissen zur Harmonischen Reihe zurück. Wir fragen uns: ''Wie hoch ist die Wahrscheinlichkeit, dass zwei beliebige Elemente (nennen wir sie <math>z_i</math> und <math>z_j</math>, wobei <math>z_i < z_j</math>) im Laufe des gesamten Algorithmus direkt miteinander verglichen werden?''
* Zwei Elemente werden genau dann miteinander verglichen, wenn eines der beiden als Pivot-Element ausgewählt wird, '''bevor''' irgendein anderes Element, dessen Wert zwischen <math>z_i</math> und <math>z_j</math> liegt, als Pivot gewählt wird.
* Zwischen <math>z_i</math> und <math>z_j</math> (inklusive der beiden Randelemente) liegen exakt <math>k = j - i + 1</math> Elemente.
* Gehen wir von einer zufälligen Pivot-Wahl aus, hat jedes dieser <math>k</math> Elemente die gleiche Chance, zuerst als Pivot gezogen zu werden. Damit <math>z_i</math> und <math>z_j</math> verglichen werden, muss exakt <math>z_i</math> oder <math>z_j</math> der "Gewinner" dieser Ziehung sein. Da es <math>2</math> günstige Fälle bei <math>k</math> möglichen Fällen gibt, beträgt die Wahrscheinlichkeit exakt <math>\frac{2}{k}</math>.
Summieren wir diese Wahrscheinlichkeiten (den sogenannten Erwartungswert) für alle möglichen Elementpaare im gesamten Array auf, erhalten wir folgende Doppel-Summe:
<math>E(X) = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j - i + 1}</math>
Ersetzt man den Abstand <math>(j - i + 1)</math> formal durch die Laufvariable <math>k</math>, löst sich die innere Summe auf zu:
<math>\sum_{k=2}^{n} \frac{2}{k} = 2 \cdot \left( \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right)</math>
In der Klammer erkennen wir exakt die '''Harmonische Reihe''' wieder! Aus der Mathematik wissen wir, dass die Harmonische Reihe für große <math>n</math> gegen den natürlichen Logarithmus <math>\ln(n)</math> konvergiert. Die innere Summe ergibt also maximal ungefähr <math>2 \cdot \ln(n)</math>. Da die äußere Summe (die Variable <math>i</math>) insgesamt <math>n</math>-mal durchlaufen wird, multiplizieren wir diesen Wert mit <math>n</math> und erhalten insgesamt rund <math>2n \cdot \ln(n)</math> zu erwartende Vergleiche.
Da konstante Vorfaktoren (wie die <math>2</math>) und die Basis des Logarithmus in der asymptotischen Notation ignoriert werden, ist der Beweis erbracht:
'''Fazit Average-Case:''' Auch bei zufälliger Verteilung konvergiert Quicksort dank des logarithmischen Wachstums sicher gegen die Komplexitätsklasse <math>\mathcal{O}(n \log n)</math>.
=== Worst-Case (Schlechtester Fall) ===
[[Datei:Baum N-Ebenen.png|mini|Worst-Case: Entarteter Baum]]
Angenommen, wir haben extremes Pech und die Partitionierung ist maximal unausgeglichen. Das gewählte Pivot ist immer das absolut kleinste oder größte Element der aktuellen Teilliste. Dann enthält eine der Partitionen 0 Elemente und die andere Partition <math>n-1</math> Elemente. Der Baum "entartet" zu einer linearen Kette.
''Hinweis für die Praxis: Wird bei einer naiven Implementierung immer stur das letzte Element als Pivot gewählt, tritt dieser Worst-Case ironischerweise genau dann auf, wenn die Liste bereits aufsteigend oder absteigend sortiert ist!''
Der Aufwand für das Vergleichen (Partitionieren) auf der ersten Ebene mit <math>n</math> Elementen ist proportional zu <math>n</math>. Nennen wir diesen Aufwand <math>c \cdot n</math> (wobei <math>c</math> eine Konstante für die Dauer eines einzelnen Vergleichs ist).
Auf der nächsten Ebene müssen wir <math>n-1</math> Elemente vergleichen, der Aufwand ist also <math>c \cdot (n-1)</math>. Danach <math>c \cdot (n-2)</math> und so weiter.
Wenn wir die Partitionierungszeiten für alle Ebenen aufsummieren, erhalten wir folgende Reihe:
<math>c \cdot n + c \cdot (n - 1) + c \cdot (n - 2) + \dots + c \cdot 2</math>
Wir klammern <math>c</math> aus und erkennen die bekannte [[Arithmetische-reihe|Gaußsche Summenformel]]:
<math>c \cdot (n + (n-1) + (n-2) + \dots + 2) \approx c \cdot \frac{n(n+1)}{2} = \frac{c}{2}n^2 + \frac{c}{2}n</math>
Da in der asymptotischen Laufzeitanalyse konstante Faktoren (<math>\frac{c}{2}</math>) und niederwertige Terme (wie <math>n</math>) ignoriert werden, bestimmt allein der quadratische Term das Wachstumsverhalten.
'''Fazit Worst-Case:''' Quicksort hat im schlechtesten Fall eine Zeitkomplexität von <math>\mathcal{O}(n^2)</math>.
[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_TP2]]
Abgerufen von „https://wiki.flbk-hamm.de/Quicksort“