Quicksort

Flbkwikiadmin — Tue, 05 May 2026 07:28:30 GMT

Laufzeitanalyse

Angebotsvergleich

Flbkwikiadmin — Thu, 30 Apr 2026 08:12:41 GMT

Beispiele

← Nächstältere Version		Version vom 30. April 2026, 10:12 Uhr
Zeile 11:		Zeile 11:

	==Beispiele==		==Beispiele==
	Wir betrachten im ~~folgenden~~ zwei Beispiele für einen Angebotsvergleich.		Wir betrachten im Folgenden zwei Beispiele für einen Angebotsvergleich.

	===Angebotsvergleich mit Barwerten durchführen===		===Angebotsvergleich mit Barwerten durchführen===
	Wir haben uns ein Fahrrad gekauft. Der Zinssatz beträgt 4 % pro Jahr. Es besteht die Möglichkeit in einem Jahr 450 € oder in zwei Jahren 480 € zu zahlen.		Wir haben uns ein Fahrrad gekauft. Der Zinssatz beträgt 4 % pro Jahr. Es besteht die Möglichkeit, in einem Jahr 450 € oder in zwei Jahren 480 € zu zahlen.

	Wir verwenden die [[Zinseszinsrechnung#Zinseszinsformel\|Zinseszinsformel]] und berechnen jeweils das [[Zinseszinsrechnung\|Anfangskapital]]:		Wir verwenden die [[Zinseszinsrechnung#Zinseszinsformel\|Zinseszinsformel]] und berechnen jeweils das [[Zinseszinsrechnung\|Anfangskapital]]:

	#Möglichkeit mit <math>q=1,04,~n=1 \text{ und } K(1)=450</math>: <br><math>K(n)=K(0)\cdot q^n</math><br><math>450=K(0)\cdot 1,04^1~\|~:1,04</math><br><math>\frac{450}{{1,04}}=K(0)</math><br><math>432,69\approx K(0)</math>		#Möglichkeit mit <math>q=1,04,~n=1 \text{ und } K(1)=450</math>: <br><math>K(n)=K(0)\cdot q^n</math><br><math>450=K(0)\cdot 1,04^1~\|~:1,04</math><br><math>\frac{450}{{1,04}}=K(0)</math><br><math>432,69\approx K(0)</math>
	#Möglichkeit mit <math>q=1,04,~n=2 \text{ und } K(2)=480</math>: <br><math>K(n)=K(0)\cdot q^n</math><br><math>~~450~~=K(0)\cdot 1,04^2~\|~:1,04^2</math><br><math>\frac{~~450~~}{{1,04^2}}=K(0)</math><br><math>443,79\approx K(0)</math>		#Möglichkeit mit <math>q=1,04,~n=2 \text{ und } K(2)=480</math>: <br><math>K(n)=K(0)\cdot q^n</math><br><math>480=K(0)\cdot 1,04^2~\|~:1,04^2</math><br><math>\frac{480}{{1,04^2}}=K(0)</math><br><math>443,79\approx K(0)</math>

	Wir wählen Möglichkeit 1 ~~wählen~~, weil das Anfangskapital mit ca. 432,69 € geringer ist als das Anfangskapital ~~über~~ 443,79 € bei Möglichkeit 2.		Wir wählen Möglichkeit 1, weil das Anfangskapital mit ca. 432,69 € geringer ist als das Anfangskapital von 443,79 € bei Möglichkeit 2.

	===Angebotsvergleich ohne Barwerte durchführen===		===Angebotsvergleich ohne Barwerte durchführen===
	Wir haben uns ein Fahrrad gekauft. Der Zinssatz beträgt 4 % pro Jahr. Es besteht die Möglichkeit in einem Jahr 450 € oder in zwei Jahren 480 € zu zahlen.		Wir haben uns ein Fahrrad gekauft. Der Zinssatz beträgt 4 % pro Jahr. Es besteht die Möglichkeit, in einem Jahr 450 € oder in zwei Jahren 480 € zu zahlen.

	Alternativ zur vorherigen Rechnung können wir die Zahlungen aufzinsen und anschließend vergleichen:		Alternativ zur vorherigen Rechnung können wir die Zahlungen aufzinsen und anschließend vergleichen:

← 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>.

FLBK-Wiki - Letzte Änderungen [de]

Quicksort

Angebotsvergleich