FLBK-Wiki

Quicksort: Unterschied zwischen den Versionen

← Zum vorherigen VersionsunterschiedZum nächsten Versionsunterschied →
Flbkwikiadmin (Diskussion | Beiträge)
Bürokraten, Oberflächenadministratoren, Administratoren
2.195 Bearbeitungen
VisuellWikitext
Keine Bearbeitungszusammenfassung
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>
</syntaxhighlight>
== Laufzeitanalyse ==
== Laufzeitanalyse ==
=== Worst-Case ===
[[Datei:Baum N-Ebenen.png|mini]]
Betrachten wir zunächst die Worst-Case-[[Laufzeitanalyse]]. Angenommen, wir haben wirklich Pech und die Partitionsgrößen sind wirklich unausgeglichen. Angenommen, der von der Partitionsfunktion ausgewählte Drehpunkt ist immer entweder das kleinste oder das größte Element im Subarray für n-Elemente. Dann enthält eine der Partitionen keine Elemente und die andere Partition enthält n-1 Elemente - alle außer dem Pivot. Die rekursiven Aufrufe erfolgen also auf Subarrays der Größen 0 und n-1.


In diesem Szenario benötigt [[Rekursion|rekursive]] Aufruf von n-1  Elementen c* (n - 1) für eine Konstante c. Dies Konstante c repräsentiert die Benötigte Zeit für eine Operation wie einen Aufruf oder einen Vergleich. Für n-2 Elemente werden die Zeit c*(n-2) benötigt und so weiter (siehe Abbildung).
=== Worst-Case (Schlechtester Fall) ===
[[Datei:Baum N-Ebenen.png|mini|Worst-Case: Entarteter Baum]]
Betrachten wir zunächst die Worst-Case-[[Laufzeitanalyse]]. Angenommen, wir haben extremes Pech und die Partitionierung ist maximal unausgeglichen. Das gewählte Pivot ist immer das absolut kleinste oder größte Element. Dann enthält eine der Partitionen 0 Elemente und die andere Partition <math>n-1</math> Elemente.  


Wenn wir die Partitionierungszeiten für jede Ebene aufsummieren, erhalten wir nach der [[Arithmetische-reihe|gauschen Summenformel]]:
Der Aufwand für das Vergleichen (Partitionieren) einer 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 Vergleichs ist).
<math>cn+c(n−1)+c(n−2)+⋯+2c = c(n+(n−1)+(n−2)+⋯+2) =c((n+1)(n/2)−1)</math>  
Auf der nächsten Ebene müssen wir <math>n-1</math> Elemente vergleichen, der Aufwand ist <math>c \cdot (n-1)</math>. Danach <math>c \cdot (n-2)</math> und so weiter.
Im Rahmend er [[Laufzeitanalyse]] ignorieren wir Terme niedriger Ordnung und konstante Koeffizienten. In der Big-Θ-Notation folgt hieraus die Worst-Case-Laufzeit von QuickSort <math> O(n^2)</math>.


== Best Case ==
Wenn wir die Partitionierungszeiten für alle Ebenen aufsummieren, erhalten wir folgende Reihe:
[[Datei:Verzweigungsbaum Quicksort symetrisch.png|mini]]
<math>c \cdot n + c \cdot (n - 1) + c \cdot (n - 2) + \dots + c \cdot 2</math>
Der beste Fall von Quicksort liegt vor, wenn die Partitionen so gleichmäßig wie möglich aufgeteilt werden: Ihre Größen sind entweder gleich oder weichen nur um ein Element  voneinander ab.


[[Datei:SubArrays symetrisch Quicksort.png|mini]]
Wir klammern <math>c</math> aus und erkennen die bekannte [[Arithmetische-reihe|Gaußsche Summenformel]]:
Der erstere Fall tritt auf, wenn das Subarray eine ungerade Anzahl von Elementen hat und der Drehpunkt nach der Partitionierung genau in der Mitte liegt und jede Partition <math>(n-1) / 2 </math> hat.  Der letztere Fall tritt auf, wenn das Subarray eine gerade Anzahl n von Elementen hat und eine Partition n / 2 hat, während die andere n-1 / 2 hat. In beiden Fällen hat jede Partition höchstens n / 2 Elemente.
<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 asymtotischen Laufzeitanalyse konstante Faktoren und kleinere Terme (wie <math>n</math>) ignoriert werden, wächst der Aufwand quadratisch.
'''Fazit Worst-Case:''' Quicksort hat im schlechtesten Fall eine Zeitkomplexität von <math>\mathcal{O}(n^2)</math>.
 
=== 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 immer exakt in der Mitte teilt. Die 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>.


Wird die Anzahl  der zu sortierenden Elemente n verdoppelt, muss nur eine neue Ebene mit Teilarrays erzeugt werden. Dieses Wachstum lässt sich mit <math>log(n) </math> beschreiben.
{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
|-
|-
! Zu sortierende Elemente n
! Zu sortierende Elemente <math>n</math>
| style="color:green" | 4
| style="color:green" | 4
| style="color:green" | 8
| style="color:green" | 8
Zeile 117: Zeile 154:
| style="color:green" | 32
| style="color:green" | 32
|-
|-
! Zu sortierende Elemente n
! Als Zweierpotenz
| <math>\color{green}{2^2}</math>
| <math>\color{green}{2^2}</math>
| <math>\color{green}{2^3}</math>
| <math>\color{green}{2^3}</math>
Zeile 123: Zeile 160:
| <math>\color{green}{2^5}</math>
| <math>\color{green}{2^5}</math>
|-
|-
! Anzahl Ebene log(n)
! Anzahl Rekursionsebenen <math>\log_2(n)</math>
| style="color:red" | 2
| style="color:red" | 2
| style="color:red" | 3
| style="color:red" | 3
Zeile 130: Zeile 167:
|}
|}


In jeder Ebene müssen n Elemente sortiert werden. Hieraus ergibt sich eine Laufzeit von <math> O(n * log(n))</math>.
Wir haben also insgesamt <math>\log_2(n)</math> Ebenen. Auf '''jeder einzelnen Ebene''' müssen in der Summe <math>n</math> Elemente betrachtet und mit dem jeweiligen Pivot verglichen werden.  
Wir multiplizieren also die Arbeit pro Ebene (<math>n</math>) 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 selten den perfekten Best-Case, aber fast nie den absoluten Worst-Case. Meistens teilt das Pivot die Liste beispielsweise im Verhältnis 30:70 oder 60:40.
 
Um den Average-Case mathematisch exakt zu beweisen, greifen wir auf das Prinzip der '''Indikatorvariablen''' und der '''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>) im Laufe des Algorithmus miteinander verglichen werden?''
 
* Zwei Elemente werden genau dann miteinander verglichen, wenn eines der beiden als Pivot-Element ausgewählt wird, '''bevor''' irgendein Element, dessen Wert zwischen den beiden liegt, als Pivot gewählt wird.
* Sind die Daten völlig zufällig verteilt, ist die Wahrscheinlichkeit, dass von <math>k</math> Elementen genau das größte oder kleinste zuerst als Pivot gewählt wird, exakt <math>\frac{2}{k}</math>.
 
Summieren wir diese Wahrscheinlichkeiten (Erwartungswert) für alle Elementpaare im 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>
 
Setzt man für den Abstand <math>(j - i + 1)</math> eine neue Variable <math>k</math> ein, 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>
 
Hier erkennen wir exakt die '''Harmonische Reihe''' (<math>H_n</math>) wieder, die wir bereits bei der Maximumsuche kennengelernt haben! Da die Harmonische Reihe für große <math>n</math> gegen den natürlichen Logarithmus <math>\ln(n)</math> konvergiert, ergibt die innere Summe ungefähr <math>2 \cdot \ln(n)</math>. Da die äußere Summe <math>n</math>-mal läuft, erhalten wir insgesamt rund <math>2n \cdot \ln(n)</math> Vergleiche.
 
Da Konstanten wie der Faktor 2 beim Groß-O ignoriert werden, ist nun stochastisch bewiesen:
'''Fazit Average-Case:''' Auch bei zufälliger Verteilung konvergiert Quicksort dank des logarithmischen Wachstums der harmonischen Reihe sicher gegen die Komplexitätsklasse <math>\mathcal{O}(n \log n)</math>.
 
[[Kategorie:Programmierung]]
[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_TP2]]
[[Kategorie:FI_I_TP2]]
Abgerufen von „https://wiki.flbk-hamm.de/Quicksort“