Quicksort - Versionsgeschichte

Flbkwikiadmin: /* Laufzeitanalyse */

2026-05-05T07:28:30Z

Laufzeitanalyse

Flbkwikiadmin: /* Laufzeitanalyse */

2026-04-28T08:51:30Z

Laufzeitanalyse

@@ Zeile 155: / Zeile 155: @@
 == Laufzeitanalyse ==
 === Best-Case (Bester Fall) ===
@@ Zeile 223: / Zeile 207: @@
 Da konstante Vorfaktoren wie die <math>2</math> 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:AHR_I_Informatik_LK]]
 [[Kategorie:FI_I_TP2]]

Flbkwikiadmin am 20. April 2026 um 10:26 Uhr

2026-04-20T10:26:21Z

← Nächstältere Version		Version vom 20. April 2026, 12:26 Uhr
Zeile 121:		Zeile 121:
	</syntaxhighlight>		</syntaxhighlight>

	== ~~Maximumsuche~~ ==		== Vorbereitung: Indikatorvariablen und die Harmonische Reihe ==
	Bei komplexeren Algorithmen wie [[Quicksort]] reicht einfaches Zählen nicht mehr aus. Hier arbeiten wir mit einem ~~mathematischen Trick~~: '''Indikatorvariablen''' und der '''Harmonischen Reihe'''. Um das zu ~~verstehen~~, analysieren wir einen simplen Code zur Maximumsuche:		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">		<syntaxhighlight lang="java">
Zeile 135:		Zeile 135:
	}		}
	</syntaxhighlight>		</syntaxhighlight>
	Die Vergleiche in der <code>if</code>-Bedingung werden immer <math>n-1</math> Mal ausgeführt. Aber wie oft wird die Variable <code>max</code> im Durchschnitt überschrieben (Update-Operation)?		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.		Wir stellen uns vor, das Array enthält völlig zufällig gemischte Zahlen.
	* '''Intuitiver Ansatz:'''		* '''Intuitiver Ansatz:'''
	Das 1. Element ist automatisch das bisherige Maximum (Wahrscheinlichkeit: 1).		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 exakt 50% (<math>\frac{1}{2}</math>).		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>.		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>.

Zeile 152:		Zeile 152:
	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>).		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 ~~später selbst~~ zu beweisen, dass Quicksort im Average-Case bei <math>\mathcal{O}(n \log n)</math> liegt.		'''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 ==		== Laufzeitanalyse ==
Zeile 169:		Zeile 169:
	<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>		<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.		Da in der asymptotischen 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>.		'''Fazit Worst-Case:''' Quicksort hat im schlechtesten Fall eine Zeitkomplexität von <math>\mathcal{O}(n^2)</math>.

Zeile 205:		Zeile 205:

	=== Average-Case (Durchschnittlicher Fall) ===		=== 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.		In der Praxis haben wir selten den perfekten Best-Case, aber fast nie den absoluten Worst-Case. Meistens teilt das Pivot die Liste in ungleiche, aber moderate Verhältnisse (z. B. 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?''		Um den Average-Case mathematisch exakt zu beweisen, greifen wir auf unser Vorwissen (Indikatorvariablen und Harmonische 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 Algorithmus direkt 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.		* 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.
	* 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>.		* Zwischen <math>z_i</math> und <math>z_j</math> (inklusive der beiden Randelemente) liegen exakt <math>k = j - i + 1</math> Elemente.
			* Sind die Daten völlig zufällig verteilt, hat jedes dieser <math>k</math> Elemente die gleiche Chance, zuerst als Pivot gewählt 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 (<math>z_i</math> oder <math>z_j</math>) bei <math>k</math> möglichen Fällen gibt, beträgt die Wahrscheinlichkeit exakt <math>\frac{2}{k}</math>.

	Summieren wir diese Wahrscheinlichkeiten (Erwartungswert) für alle Elementpaare im Array auf, erhalten wir folgende Doppel-Summe:		Summieren wir diese Wahrscheinlichkeiten (den 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>		<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:		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>		<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.		Hier erkennen wir exakt die '''Harmonische Reihe''' (<math>H_n</math>) wieder! 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 (stark vereinfacht) <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:		Da konstante Vorfaktoren wie die <math>2</math> 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>.		'''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>.

Flbkwikiadmin am 20. April 2026 um 07:39 Uhr

2026-04-20T07:39:38Z

@@ Zeile 120: / Zeile 120: @@
+}
 </syntaxhighlight>
 == Laufzeitanalyse ==

Flbkwikiadmin am 20. April 2026 um 07:37 Uhr

2026-04-20T07:37:11Z

Änderungen zeigen

Thomas: /* Best Case */

2026-02-20T10:59:49Z

Best Case

← Nächstältere Version		Version vom 20. Februar 2026, 12:59 Uhr
Zeile 131:		Zeile 131:

	In jeder Ebene müssen n Elemente sortiert werden. Hieraus ergibt sich eine Laufzeit von <math> O(n * log(n))</math>.		In jeder Ebene müssen n Elemente sortiert werden. Hieraus ergibt sich eine Laufzeit von <math> O(n * log(n))</math>.
			[[Kategorie:Programmierung]]
			[[Kategorie:AHR_I_Informatik_LK]]
			[[Kategorie:FI_I_TP2]]

Thomas: /* Worst-Case */

2026-02-20T09:46:42Z

Worst-Case

← Nächstältere Version		Version vom 20. Februar 2026, 11:46 Uhr
Zeile 99:		Zeile 99:
	Wenn wir die Partitionierungszeiten für jede Ebene aufsummieren, erhalten wir nach der [[Arithmetische-reihe\|gauschen Summenformel]]:		Wenn wir die Partitionierungszeiten für jede Ebene aufsummieren, erhalten wir nach der [[Arithmetische-reihe\|gauschen Summenformel]]:
	<math>cn+c(n−1)+c(n−2)+⋯+2c = c(n+(n−1)+(n−2)+⋯+2) =c((n+1)(n/2)−1)</math>		<math>cn+c(n−1)+c(n−2)+⋯+2c = c(n+(n−1)+(n−2)+⋯+2) =c((n+1)(n/2)−1)</math>
	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>.		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 ==		== Best Case ==

Thomas: /* Laufzeitanalyse */

2026-02-20T09:46:23Z

Laufzeitanalyse

← Nächstältere Version		Version vom 20. Februar 2026, 11:46 Uhr
Zeile 93:		Zeile 93:
	=== Worst-Case ===		=== Worst-Case ===
	[[Datei:Baum N-Ebenen.png\|mini]]		[[Datei:Baum N-Ebenen.png\|mini]]
	Betrachten wir zunächst die Worst-Case-~~Laufzeitanalyseaufzeit~~. 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.		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).		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).

Thomas am 20. Februar 2026 um 09:45 Uhr

2026-02-20T09:45:18Z

← Nächstältere Version		Version vom 20. Februar 2026, 11:45 Uhr
Zeile 100:		Zeile 100:
	<math>cn+c(n−1)+c(n−2)+⋯+2c = c(n+(n−1)+(n−2)+⋯+2) =c((n+1)(n/2)−1)</math>		<math>cn+c(n−1)+c(n−2)+⋯+2c = c(n+(n−1)+(n−2)+⋯+2) =c((n+1)(n/2)−1)</math>
	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>.		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 ==
			[[Datei:Verzweigungsbaum Quicksort symetrisch.png\|mini]]
			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]]
			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.

			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"
			\|-
			! Zu sortierende Elemente n
			\| style="color:green" \| 4
			\| style="color:green" \| 8
			\| style="color:green" \| 16
			\| style="color:green" \| 32
			\|-
			! Zu sortierende Elemente n
			\| <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 Ebene log(n)
			\| style="color:red" \| 2
			\| style="color:red" \| 3
			\| style="color:red" \| 4
			\| style="color:red" \| 5
			\|}

			In jeder Ebene müssen n Elemente sortiert werden. Hieraus ergibt sich eine Laufzeit von <math> O(n * log(n))</math>.

Thomas am 20. Februar 2026 um 08:12 Uhr

2026-02-20T08:12:12Z

← Nächstältere Version		Version vom 20. Februar 2026, 10:12 Uhr
Zeile 90:		Zeile 90:
	}		}
	</syntaxhighlight>		</syntaxhighlight>
			== Laufzeitanalyse ==
			=== Worst-Case ===
			[[Datei:Baum N-Ebenen.png\|mini]]
			Betrachten wir zunächst die Worst-Case-Laufzeitanalyseaufzeit. 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).

			Wenn wir die Partitionierungszeiten für jede Ebene aufsummieren, erhalten wir nach der [[Arithmetische-reihe\|gauschen Summenformel]]:
			<math>cn+c(n−1)+c(n−2)+⋯+2c = c(n+(n−1)+(n−2)+⋯+2) =c((n+1)(n/2)−1)</math>
			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>.

← Nächstältere Version		Version vom 5. Mai 2026, 09:28 Uhr
Zeile 158:		Zeile 158:
	=== Best-Case (Bester Fall) ===		=== Best-Case (Bester Fall) ===
	[[Datei:Verzweigungsbaum Quicksort symetrisch.png\|mini\|Best-Case: Symmetrischer Baum]]		[[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ß.		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]]		[[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 <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"		{\| class="wikitable" style="text-align:center"
Zeile 184:		Zeile 184:
	\|}		\|}

	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 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>) mit der Anzahl der Ebenen (<math>\log_2(n)</math>).
			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>.		'''Fazit Best-Case:''' Die Laufzeit beträgt <math>\mathcal{O}(n \log n)</math>.

	=== Average-Case (Durchschnittlicher Fall) ===		=== 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 in ungleiche, aber moderate Verhältnisse (z. B. 30:70 oder 60:40).		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 unser Vorwissen ~~(Indikatorvariablen und Harmonische~~ 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 Algorithmus direkt miteinander verglichen werden?''		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.		* 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.		* Zwischen <math>z_i</math> und <math>z_j</math> (inklusive der beiden Randelemente) liegen exakt <math>k = j - i + 1</math> Elemente.
	* ~~Sind die Daten völlig zufällig verteilt~~, hat jedes dieser <math>k</math> Elemente die gleiche Chance, zuerst als Pivot ~~gewählt~~ 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 ~~(<math>z_i</math> oder <math>z_j</math>)~~ bei <math>k</math> möglichen Fällen gibt, beträgt die Wahrscheinlichkeit exakt <math>\frac{2}{k}</math>.		* 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 Erwartungswert) für alle möglichen Elementpaare im gesamten Array auf, erhalten wir folgende Doppel-Summe:		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>		<math>E(X) = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j - i + 1}</math>

Zeile 203:		Zeile 204:
	<math>\sum_{k=2}^{n} \frac{2}{k} = 2 \cdot \left( \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right)</math>		<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! 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 (~~stark vereinfacht~~) <math>n</math>-mal ~~läuft~~, erhalten ~~wir~~ insgesamt rund <math>2n \cdot \ln(n)</math> Vergleiche.		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> ~~beim Groß-O~~ ignoriert werden, ist ~~nun stochastisch bewiesen~~:		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 ~~der harmonischen Reihe~~ sicher gegen die Komplexitätsklasse <math>\mathcal{O}(n \log n)</math>.		'''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) ===		=== Worst-Case (Schlechtester Fall) ===
	[[Datei:Baum N-Ebenen.png\|mini\|Worst-Case: Entarteter Baum]]		[[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.		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) ~~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).		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 <math>c \cdot (n-1)</math>. Danach <math>c \cdot (n-2)</math> und so weiter.		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:		Wenn wir die Partitionierungszeiten für alle Ebenen aufsummieren, erhalten wir folgende Reihe:
Zeile 221:		Zeile 223:
	<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>		<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 und ~~kleinere~~ Terme (wie <math>n</math>) ignoriert werden, ~~wächst~~ der ~~Aufwand quadratisch~~.		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>.		'''Fazit Worst-Case:''' Quicksort hat im schlechtesten Fall eine Zeitkomplexität von <math>\mathcal{O}(n^2)</math>.