FLBK-Wiki - Benutzerbeiträge [de]

Quicksort

2026-05-05T07:28:30Z

Flbkwikiadmin: /* Laufzeitanalyse */

== Einführung ==
[[Datei:Rekursive Baumstruktur.jpg|mini|Rekursive Aufteilung beim Quicksort]]
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 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)].

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

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.

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 ==
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 10 8 6 11 4 9 3 1 5 2 12

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 2 5 6 1 4 '''7''' 9 11 8 10 12

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 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''' 2 5 6 1 4 7 9 11 8 10 12

Der Algorithmus sortiert die Elemente relativ zur 3 um:

1 2 '''3''' 6 5 4 7 9 11 8 10 12

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

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.

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

<syntaxhighlight lang="text">
funktion quicksort(links, rechts)
falls links < rechts dann
// teile() ordnet das Array um und liefert die finale Position des Pivots
teiler := teile(links, rechts)

// Rekursiver Aufruf für die linke Teilliste
quicksort(links, teiler - 1)

// Rekursiver Aufruf für die rechte Teilliste
quicksort(teiler + 1, rechts)
ende
ende
</syntaxhighlight>

== Wahl des Pivot-Elements ==
Die Effizienz von Quicksort steht und fällt mit der Wahl des Pivot-Elements.

* '''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.

'''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 ==
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">
public void quickSort(int array[], int links, int rechts) {
if (links < rechts) {
// Teile das Array und finde die Position des Pivot-Elements
int i = teile(array, links, 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) {
int pivot, i, j, help;
pivot = array[rechts]; // Wir wählen das rechte Randelement als Pivot
i = links;
j = rechts - 1;

// 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) {
// Tausche array[i] mit array[j], um es in den rechten Bereich zu bringen
help = array[i];
array[i] = array[j];
array[j] = help;
j--; // j einen Schritt weiter nach links schieben
} else {
i++; // i war kleiner/gleich Pivot, ist also korrekt positioniert -> weiter nach rechts
}
}

// Das Pivot-Element an seine endgültige Position (i) tauschen
help = array[i];
array[i] = array[rechts];
array[rechts] = help;

// Rückgabe der finalen Position des Pivot-Elements
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>
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]]

Angebotsvergleich

2026-04-30T08:12:41Z

Flbkwikiadmin: /* Beispiele */

Ein Angebotsvergleich wird durchgeführt, um das bestmögliche Angebot für ein Produkt oder eine Dienstleistung zu bestimmen.

==Äquivalenzprinzip der Mathematik==
Unterschiedliche Geldbeträge dürfen nur verglichen, addiert oder subtrahiert werden, wenn diese auf den gleichen Zeitpunkt auf- oder abgezinst wurden.
In der Regel beziehen wir Geldbeträge auf den jetzigen Zeitpunkt (<math>t=0</math>) und nennen den jeweiligen Geldbetrag '''Barwert'''.

==Definition==
Bei einem '''Angebotsvergleich''' liegen mehrere Angebote für ein Produkt oder eine Dienstleistung mit unterschiedlichen Zahlungsbedingungen vor. Die Zahlungsforderungen in einem Angebot werden auf den Zeitpunkt <math>t=0</math> abgezinst und anschließend miteinander addiert. Den resultierenden Wert nennen wir '''Barwert''' des Angebots. Abschließend werden die Barwerte miteinander verglichen, um das beste Angebot zu ermitteln.

<html><iframe width="280" height="157.5" src="https://www.youtube.com/embed/mPwGFaFQ5LU?si=rTdru8wzdgwR8gFU" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe></html>

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

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

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===
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:

#Möglichkeit mit <math>q=1,04,~n=1 \text{ und } K(1)=450</math>: <math>K\left(2\right)=450\cdot1,04=468</math>
#Möglichkeit mit <math>q=1,04,~n=2 \text{ und } K(2)=480</math>: <math>K\left(2\right)=480</math>

Gemäß dem Äquivalenzprinzip ist Möglichkeit 1 wieder besser.

[[Kategorie:Finanzmathematik]]
[[Kategorie:FHR_WuV_Mathe]]

Insertion-sort

2026-04-28T08:52:09Z

Flbkwikiadmin: Flbkwikiadmin verschob die Seite Insertion-sort nach Insertionsort

#WEITERLEITUNG [[Insertionsort]]

Insertionsort

2026-04-28T08:52:09Z

Flbkwikiadmin: Flbkwikiadmin verschob die Seite Insertion-sort nach Insertionsort

== Einführung ==
Der [[Algorithmus]] dieses [[Sortieren|Sortierverfahrens]] ist relativ simpel. Das Prinzip von Insertion Sort ist folgendes: Die einzelnen Elemente werden von vorne nach hinten durchlaufen. Von der aktuellen Position aus wird jedes Element von rechts nach links verschoben – und zwar so lange, bis das einzufügende Element größer oder gleich dem Element ist, das an der aktuell betrachteten Position steht.

Der Platz für das Element, das verschoben wird, ist währenddessen frei. Diese Lücke wird anschließend mit dem entsprechenden Wert an der richtigen Stelle gefüllt.

== Beispiel ==
[[Datei:Animation Insertio-Sort.gif|mini]]
Die folgende Tabelle zeigt die Sortierschritte zum Sortieren der Folge 5 7 0 3 4 2 6 1. Auf der linken Seite (grün dargestellt) befindet sich jeweils der bereits sortierte Teil der Folge. Die blauen Ziffern repräsentieren den unsortierten Teil der Zahlenfolge. Ganz rechts steht in Klammern die Anzahl der Positionen, um die das eingefügte Element nach links verschoben wurde. Das aktuell eingefügte Element ist fett markiert.

{| class="wikitable" style="text-align:center; font-family:monospace;"
|-
| ''5'' || 7 || 0 || 3 || 4 || 2 || 6 || 1 || (0)
|-
| '''5''' || '''7''' || 0 || 3 || 4 || 2 || 6 || 1 || (0)
|-
| '''''0''''' || 5 || 7 || 3 || 4 || 2 || 6 || 1 || (2)
|-
| 0 || '''''3''''' || 5 || 7 || 4 || 2 || 6 || 1 || (2)
|-
| 0 || 3 || '''''4''''' || 5 || 7 || 2 || 6 || 1 || (2)
|-
| 0 || '''''2''''' || 3 || 4 || 5 || 7 || 6 || 1 || (4)
|-
| 0 || 2 || 3 || 4 || 5 || '''''6''''' || 7 || 1 || (1)
|-
| 0 || '''''1''''' || 2 || 3 || 4 || 5 || 6 || 7 || (6)
|}

== Pseudocode ==
Der [[Algorithmus]] sieht im Pseudocode so aus:

<syntaxhighlight lang="text">
prozedur insertionSort(A ist Liste sortierbarer Elemente)
n = Länge von A
für i von 1 bis n - 1 wiederhole
einzusortierenderWert = A[i]
j = i - 1
solange j ≥ 0 und A[j] > einzusortierenderWert wiederhole
A[j + 1] = A[j]
j = j - 1
ende solange
A[j + 1] = einzusortierenderWert
ende für
ende prozedur
</syntaxhighlight>

== Komplexität ==

=== Best Case ===
Die optimale Eingabe ist ein bereits sortiertes [[Array]]. In diesem Fall wird pro Iteration lediglich ein Vergleich durchgeführt, und die innere Schleife wird nie betreten. Die Gesamtanzahl der Vergleiche ist somit proportional zur Anzahl der Elemente <math>n</math>.

Insertion Sort besitzt im Best Case daher eine lineare Laufzeit von <math>O(n)</math>.

=== Average Case ===
Das Average-Case-Szenario geht von einer zufälligen Verteilung der Werte in der Liste aus.

Im Durchschnitt ist das aktuell betrachtete Element kleiner als die Hälfte der bereits sortierten Elemente. Die innere Schleife muss das Element also im Mittel nur bis in die Mitte des bisher sortierten Teilbereichs verschieben. Die Anzahl der Vergleiche und Verschiebungen halbiert sich im Vergleich zum Worst Case dadurch in etwa.

Da in der asymptotischen Landau-Notation konstante Faktoren (wie diese Halbierung) ignoriert werden, dominiert weiterhin die höchste Potenz das Wachstum. Die Zeitkomplexität liegt im Average Case demnach bei <math>O(n^2)</math>.

=== Worst Case ===
Eine Liste in umgekehrter (absteigender) Reihenfolge stellt das Worst-Case-Szenario für Insertion Sort dar, beispielsweise:

<math>[11, 7, 5, 3, 2, 0]</math>

Wir betrachten nur die Vergleichsoperationen, die mit der Variablen <math>c</math> gezählt werden. Die Anzahl der zu sortierenden Elemente beträgt <math>n</math>.

Beim ersten äußeren Schleifendurchlauf ist <math>c = 1</math>, da nur ein Vergleich durchgeführt wird. Beim zweiten Durchlauf sind es 2 Vergleiche, beim dritten 3 usw., bis zum letzten Durchlauf mit <math>n - 1</math> Vergleichen.

Die Gesamtanzahl der Vergleiche ergibt sich zu:

<math>1 + 2 + 3 + \dots + (n - 1)</math>

Dies ist eine [[Arithmetische-reihe|arithmetische Reihe]]. Mit der gaußschen Summenformel erhält man:

<math>\frac{n(n-1)}{2}</math>

Für große <math>n</math> dominiert der quadratische Term, sodass Insertion Sort im Worst Case in der Komplexitätsklasse <math>O(n^2)</math> liegt.

[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_TP2]]

Selection-sort

2026-04-28T08:51:59Z

Flbkwikiadmin: Flbkwikiadmin verschob die Seite Selection-sort nach Selectionsort

#WEITERLEITUNG [[Selectionsort]]

Selectionsort

2026-04-28T08:51:59Z

Flbkwikiadmin: Flbkwikiadmin verschob die Seite Selection-sort nach Selectionsort

== Einführung ==
Ein einfacher [[Sortieren|Sortieralgorithmus]] ist der Selection Sort (Sortieren durch Auswählen). Dieser Algorithmus sucht zunächst das kleinste Element in der Liste, merkt es sich und tauscht es mit dem Element am Anfang aus, sodass sich das kleinste Element an der ersten Stelle befindet.

Anschließend wird das zweitkleinste Element im verbleibenden, noch unsortierten Teil der Liste gesucht und mit dem Element an der zweiten Stelle vertauscht, und so weiter. Auf diese Weise erhalten die Elemente auf der linken Seite der aktuellen Position schrittweise ihren festen Platz und werden nicht mehr verändert.

== Beispiel ==
[[Datei:Array Selectionsort.gif|mini]]
Es soll eine Liste mit dem Inhalt <code>[4, 3, 1, 5, 2]</code> sortiert werden.

Im ersten Durchlauf wird die komplette Liste durchsucht, um das kleinste Element auszuwählen (Select) und an den Beginn der Liste zu stellen. In diesem Beispiel ist das der Wert 1. Der ursprüngliche Wert der Startposition (hier die 4) wird mit dem Wert an der Position des kleinsten Elements (hier die 1 am Index 2) vertauscht.

[[Datei:Animation Selectionsort.gif|mini]]
Im zweiten Durchlauf beginnt die Suche nach dem kleinsten Element nun bei Index 1. An Index 0 befindet sich bereits das kleinste Element der gesamten Liste, daher ist dort keine Suche mehr erforderlich. Der restliche Teil der Liste wird durchsucht. Es wird die 2 als kleinstes Element ausgewählt und mit der neuen Startposition vertauscht.

Die Suche wiederholt sich nach diesem Prinzip, bis alle Elemente sortiert sind. Der Suchbereich verkleinert sich dabei Schritt für Schritt um ein Element. Die folgende Animation visualisiert den Algorithmus.

== Pseudocode ==
Der [[Algorithmus]] sieht im Pseudocode so aus:

<syntaxhighlight lang="text">
prozedur selectionSort(A ist Liste sortierbarer Elemente)
n = Länge von A
für einfuegeIndex von 0 bis n - 2 wiederhole
minPosition = einfuegeIndex
für idx von einfuegeIndex + 1 bis n - 1 wiederhole
falls A[idx] < A[minPosition] dann
minPosition = idx
ende falls
ende für
falls minPosition ≠ einfuegeIndex dann
vertausche A[minPosition] und A[einfuegeIndex]
ende falls
ende für
ende prozedur
</syntaxhighlight>

== Java-Implementierung ==
<syntaxhighlight lang="java">
public ArrayList<Mitarbeiter> sortierenNachNachnamen() {
ArrayList<Mitarbeiter> sortierteListe = new ArrayList<>(mitarbeiterListe);
int stelle = 0;

while (stelle < sortierteListe.size() - 1) {
int kleinstesElement = stelle;

for (int index = stelle + 1; index < sortierteListe.size(); index++) {
if (sortierteListe.get(index).getNachname()
.compareTo(sortierteListe.get(kleinstesElement).getNachname()) < 0) {
kleinstesElement = index;
}
}

if (kleinstesElement != stelle) {
Mitarbeiter puffer = sortierteListe.get(kleinstesElement);
sortierteListe.set(kleinstesElement, sortierteListe.get(stelle));
sortierteListe.set(stelle, puffer);
}

stelle++;
}

return sortierteListe;
}
</syntaxhighlight>

== Komplexität ==
Mit Hilfe der [[Laufzeitanalyse]] betrachten wir nun die Zeitkomplexität des Algorithmus Selection Sort.

Ein besonderes Merkmal dieses Algorithmus ist, dass seine Laufzeit **unabhängig** von der anfänglichen Sortierung der Elemente ist. Um eine Datenstruktur (z. B. ein [[Array]]) mit <math>n</math> Einträgen zu sortieren, muss <math>n - 1</math> Mal das Minimum durch Vergleichen bestimmt werden.

Bei der ersten Bestimmung des Minimums sind <math>n - 1</math> Vergleiche notwendig, bei der zweiten <math>n - 2</math> Vergleiche, und so weiter bis zum letzten Durchlauf mit exakt 1 Vergleich. Mit der [[Arithmetische-reihe|gaußschen Summenformel]] erhält man die Gesamtanzahl der immer notwendigen Vergleiche:

<math>(n - 1) + (n - 2) + \dots + 1 = \frac{n(n - 1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n</math>

=== Best Case ===
Das Best-Case-Szenario tritt ein, wenn das Array bereits vollständig aufsteigend sortiert ist.
Auch wenn alle Elemente bereits am richtigen Platz stehen, "weiß" der Selection Sort dies nicht. Er muss trotzdem in jedem Durchlauf den kompletten unsortierten Rest der Liste überprüfen, um sicherzustellen, dass nicht doch ein noch kleineres Element existiert. Es finden zwar keine Vertauschungen (Swaps) statt, die Anzahl der Vergleiche bleibt jedoch bei <math>\frac{n(n - 1)}{2}</math>. Da die Vergleiche asymptotisch dominieren, liegt die Zeitkomplexität im Best Case bei <math>\mathcal{O}(n^2)</math>.

=== Average Case ===
Im durchschnittlichen Fall (Average Case) liegt eine zufällig durchmischte Liste vor.
Genau wie im Best Case muss der Selection Sort die gesamte arithmetische Reihe an Vergleichen durchführen, um das Minimum in jedem Schritt zu finden. Die Anzahl der durchgeführten Vertauschungen liegt im Schnitt zwischen 0 und <math>n - 1</math>. Auch hier ändert dies nichts an der dominanten quadratischen Anzahl der Vergleiche. Die Zeitkomplexität im Average Case ist somit ebenfalls <math>\mathcal{O}(n^2)</math>.

=== Worst Case ===
Das Worst-Case-Szenario liegt vor, wenn die Liste in umgekehrter (absteigender) Reihenfolge sortiert ist.
Der Algorithmus führt wieder exakt <math>\frac{n(n - 1)}{2}</math> Vergleiche aus. In diesem Fall muss bei fast jedem Durchlauf (maximal <math>n - 1</math> Mal) das kleinste Element mit dem aktuellen Start-Element vertauscht werden. Da die maximale Anzahl der Vertauschungen linear (<math>\mathcal{O}(n)</math>) wächst, die Anzahl der Vergleiche jedoch quadratisch, bestimmt der quadratische Term das Laufzeitverhalten. Die Komplexitätsklasse im Worst Case liegt demnach bei <math>\mathcal{O}(n^2)</math>.

[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_TP2]]

Bubble-sort

2026-04-28T08:51:48Z

Flbkwikiadmin: Flbkwikiadmin verschob die Seite Bubble-sort nach Bubblesort

#WEITERLEITUNG [[Bubblesort]]

Bubblesort

2026-04-28T08:51:48Z

Flbkwikiadmin: Flbkwikiadmin verschob die Seite Bubble-sort nach Bubblesort

== Einführung ==
Der Bubble Sort (Sortieren durch Aufsteigen) ist ein verhältnismäßig einfacher [[Sortieren|Sortieralgorithmus]]. In der sogenannten Bubble-Phase wird die Eingabeliste von links nach rechts durchlaufen. Dabei wird in jedem Schritt das aktuell betrachtete Element mit seinem rechten Nachbarn verglichen. Falls die beiden Elemente das vorgegebene Sortierkriterium verletzen (z. B. das linke größer als das rechte ist), werden sie vertauscht. Am Ende einer solchen Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe fest am Ende der Liste.

Die Bubble-Phase wird so lange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das jeweils letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da es bereits seine finale Position erreicht hat und die restliche zu sortierende Eingabe keine größeren bzw. kleineren Elemente mehr enthält.

Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Luftblasen im Wasser (daher der Name ''Bubble'') Schritt für Schritt immer weiter nach oben an das Ende der Liste. Es werden stets zwei benachbarte Zahlen miteinander in „Bubbles“ verglichen und bei Bedarf vertauscht.

== Beispiel ==
[[Datei:Animation Bubble Sort.gif|mini]]
Eine Reihe von fünf Zahlen soll aufsteigend sortiert werden. Die fett und kursiv markierten Zahlen werden jeweils miteinander verglichen. Ist die linke Zahl größer als die rechte, so werden beide vertauscht. Im ersten Durchlauf wandert somit die größte Zahl ganz nach rechts an die letzte Position. Im zweiten Durchlauf muss diese letzte Position folglich nicht mehr verglichen werden. Im dritten Durchlauf entfallen die letzten zwei Positionen, und so weiter.

'''1. Durchlauf'''
* '''''55 07''''' 78 12 42 (55 ist größer als 07 -> Tausch)
* 07 '''''55 78''''' 12 42 (55 ist nicht größer als 78 -> kein Tausch)
* 07 55 '''''78 12''''' 42 (78 ist größer als 12 -> Tausch)
* 07 55 12 '''''78 42''''' (78 ist größer als 42 -> Tausch, letzter Vergleich)

'''2. Durchlauf''' (78 ist bereits fest positioniert)
* '''''07 55''''' 12 42 78
* 07 '''''55 12''''' 42 78 (Tausch)
* 07 12 '''''55 42''''' 78 (Tausch, letzter Vergleich)

'''3. Durchlauf''' (55 und 78 sind fest positioniert)
* '''''07 12''''' 42 55 78
* 07 '''''12 42''''' 55 78 (Letzter Vergleich)

'''4. Durchlauf'''
* '''''07 12''''' 42 55 78 (Letzter Vergleich)

07 12 42 55 78 – Die Liste ist fertig sortiert.

== Pseudocode ==
Der [[Algorithmus]] sieht im Pseudocode der unoptimierten Basisvariante so aus:

<syntaxhighlight lang="text">
prozedur bubbleSort(A ist Liste sortierbarer Elemente)
n = Länge von A
wiederhole solange n > 1
n = n - 1
i = 0
wiederhole solange i < n
falls A[i] > A[i + 1] dann
tausche A[i] und A[i + 1]
ende falls
i = i + 1
ende wiederhole
ende wiederhole
ende prozedur
</syntaxhighlight>

== Komplexität ==
Mit Hilfe der [[Laufzeitanalyse]] betrachten wir nun die Zeitkomplexität des Algorithmus Bubble Sort für ein [[Array]] der Länge <math>n</math>.

=== Best Case ===
Das Best-Case-Szenario tritt ein, wenn die Liste bereits von Beginn an vollständig aufsteigend sortiert ist.
* '''Unoptimierte Variante (siehe Pseudocode):''' Auch wenn keine Vertauschungen notwendig sind, durchläuft der oben notierte Algorithmus die Liste strikt weiter. Er führt <math>\frac{n(n - 1)}{2}</math> Vergleiche aus. Die Zeitkomplexität liegt hier also bei <math>O(n^2)</math>.
* '''Optimierte Variante (Praxis-Standard):''' In der Praxis wird Bubble Sort fast immer mit einer Abbruchbedingung (z. B. einem Boolean-Flag `wurdeGetauscht`) implementiert. Findet in einem kompletten Durchlauf kein einziger Tausch statt, weiß der Algorithmus, dass die Liste sortiert ist, und bricht vorzeitig ab. In dieser optimierten Form benötigt er im Best Case nur <math>n - 1</math> Vergleiche. Die Zeitkomplexität sinkt dadurch auf eine lineare Laufzeit von <math>O(n)</math>.

=== Average Case ===
Im durchschnittlichen Fall (Average Case) liegt eine zufällig durchmischte Liste vor.
Etwa die Hälfte der maximal möglichen Vertauschungen muss durchgeführt werden. Sowohl die Anzahl der Vergleiche als auch die der Vertauschungen wachsen quadratisch zur Eingabemenge <math>n</math>. Konstante Faktoren (wie die Halbierung der Tauschoperationen) werden in der Landau-Notation ignoriert. Die Zeitkomplexität im Average Case liegt somit bei <math>O(n^2)</math>.

=== Worst Case ===
Das Worst-Case-Szenario liegt vor, wenn die Liste in umgekehrter (absteigender) Reihenfolge sortiert ist.
In diesem Fall ist das aktuell betrachtete Element immer größer als sein rechter Nachbar. Der Algorithmus muss in jedem einzelnen Schritt eine Vertauschung durchführen, da jedes Element an das andere Ende der Liste "blubbern" muss. Er führt die maximale Anzahl an Vergleichen und Vertauschungen durch: <math>\frac{n(n - 1)}{2}</math>. Da der Term mit der höchsten Potenz das Wachstum dominiert, liegt die Komplexitätsklasse des Bubble Sorts im Worst Case bei <math>O(n^2)</math>.

[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_TP2]]

Quicksort

2026-04-28T08:51:30Z

Flbkwikiadmin: /* Laufzeitanalyse */

== Einführung ==
[[Datei:Rekursive Baumstruktur.jpg|mini|Rekursive Aufteilung beim Quicksort]]
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 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)].

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

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.

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 ==
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 10 8 6 11 4 9 3 1 5 2 12

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 2 5 6 1 4 '''7''' 9 11 8 10 12

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 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''' 2 5 6 1 4 7 9 11 8 10 12

Der Algorithmus sortiert die Elemente relativ zur 3 um:

1 2 '''3''' 6 5 4 7 9 11 8 10 12

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

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.

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

<syntaxhighlight lang="text">
funktion quicksort(links, rechts)
falls links < rechts dann
// teile() ordnet das Array um und liefert die finale Position des Pivots
teiler := teile(links, rechts)

// Rekursiver Aufruf für die linke Teilliste
quicksort(links, teiler - 1)

// Rekursiver Aufruf für die rechte Teilliste
quicksort(teiler + 1, rechts)
ende
ende
</syntaxhighlight>

== Wahl des Pivot-Elements ==
Die Effizienz von Quicksort steht und fällt mit der Wahl des Pivot-Elements.

* '''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.

'''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 ==
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">
public void quickSort(int array[], int links, int rechts) {
if (links < rechts) {
// Teile das Array und finde die Position des Pivot-Elements
int i = teile(array, links, 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) {
int pivot, i, j, help;
pivot = array[rechts]; // Wir wählen das rechte Randelement als Pivot
i = links;
j = rechts - 1;

// 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) {
// Tausche array[i] mit array[j], um es in den rechten Bereich zu bringen
help = array[i];
array[i] = array[j];
array[j] = help;
j--; // j einen Schritt weiter nach links schieben
} else {
i++; // i war kleiner/gleich Pivot, ist also korrekt positioniert -> weiter nach rechts
}
}

// Das Pivot-Element an seine endgültige Position (i) tauschen
help = array[i];
array[i] = array[rechts];
array[rechts] = help;

// Rückgabe der finalen Position des Pivot-Elements
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>
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 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>.

{| 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. 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 in ungleiche, aber moderate Verhältnisse (z. B. 30:70 oder 60:40).

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 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.
* 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 (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>

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>

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

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

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

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

[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]
[[Kategorie:FI_I_TP2]]

Bubblesort

2026-04-28T08:50:55Z

Flbkwikiadmin:

Selectionsort

2026-04-28T08:49:46Z

Flbkwikiadmin:

2026-04-20T07:32:07Z

Flbkwikiadmin:

Laufzeitanalyse

2026-04-20T07:31:38Z

Flbkwikiadmin:

== Einführung == [[Datei:Laufzeitanalyse asymptotisch.png|mini|Asymptotische Annäherung einer Funktion]] Die Laufzeitanalyse untersucht die Zeitkomplexität eines [[Algorithmus]]. Da die reale Ausführungszeit stark von der Hardwareausstattung des Zielsystems abhängt, wird für eine allgemeine, hardwareunabhängige Betrachtung die Anzahl der elementaren [[Anweisung|Befehle]] (Operationen) analysiert, die ein Algorithmus zur Lösung eines Problems benötigt. Diese Anzahl ist abhängig von der Größe der Eingabemenge, deren Umfang auch als '''Problemgröße''' (oft <math>n</math>) bezeichnet wird. Für kleine Eingabemengen ist die Analyse häufig von geringerer Bedeutung, da auch ineffiziente [[Algorithmus|Algorithmen]] hier oft ausreichend schnelle Ergebnisse liefern. Entscheidend ist die Betrachtung für sehr große Problemgrößen, insbesondere unter ungünstigen Startbedingungen. Hier spricht man von der asymptotischen [[Programmausführung|Laufzeit]]. In Anlehnung an eine mathematische Asymptote beschreibt sie das Zeitverhalten des Algorithmus für eine potenziell unendlich wachsende Eingabemenge (z. B. eine theoretisch unendlich lange Zahlenfolge beim [[Sortieren]]). Lässt sich die Laufzeit eines Algorithmus mathematisch durch eine Funktion beschreiben, wie beispielsweise: <math>f(x) = \frac{1}{x} + x</math> So nähert sich die rot dargestellte Funktion <math>\color{red}{f(x)}</math> für große <math>x</math> der grün dargestellten Asymptote <math>\color{green}{g(x) = x}</math> an. Die Laufzeit wird in Abhängigkeit von der Länge <math>n</math> der Eingabe angegeben und für immer größer werdende <math>n</math> asymptotisch unter Verwendung der Landau-Notation (Groß-O-Notation) abgeschätzt. In der Praxis ist die Laufzeitanalyse essenziell, um entscheiden zu können, ob ein Programm bei stark anwachsenden Datenmengen noch performant und wirtschaftlich betrieben werden kann. === Abgrenzung === Es ist wichtig zu betonen, was die asymptotische Laufzeitanalyse '''nicht''' leistet: Sie misst nicht den tatsächlichen Zeitaufwand (in Sekunden) eines implementierten Algorithmus auf einem spezifischen Computer für eine konkrete, endliche Eingabemenge. == Szenarien der Laufzeitabschätzung == Man unterscheidet bei der Laufzeitabschätzung klassischerweise drei Varianten: * Das '''Worst-Case-Szenario''' (schlechtester Fall): Beschreibt diejenige Datenanordnung, die zu einer maximalen Durchlaufzeit des Algorithmus führt. Dies entspricht der oberen Schranke des Problems. * Das '''Average-Case-Szenario''' (durchschnittlicher Fall): Beschreibt eine zufällige Problemgröße und Datenanordnung, die zu einer mittleren (erwarteten) Durchlaufzeit führt. * Das '''Best-Case-Szenario''' (bester Fall): Beschreibt diejenige Datenanordnung, die zu einer minimalen Durchlaufzeit führt (z. B. eine bereits vollständig sortierte Liste). Dies entspricht der unteren Schranke. == Mathematische Berechnung des Average-Case (Erwartungswert) == Im Gegensatz zum Worst-Case oder Best-Case, die lediglich Extremfälle betrachten, ist die Berechnung des Average-Case (durchschnittlicher Fall) mathematisch anspruchsvoller. Er entspricht in der Stochastik dem '''Erwartungswert''' der Laufzeit. Um diesen zu berechnen, müssen alle möglichen Eingaben der Größe <math>n</math> sowie deren Eintrittswahrscheinlichkeiten berücksichtigt werden. Die allgemeine Formel für den Erwartungswert <math>E(T)</math> der Laufzeit lautet: <math>E(T) = \sum_{i=1}^{|E|} p_i \cdot t_i</math> Dabei ist: * <math>E</math> die Menge aller möglichen Eingaben der Größe <math>n</math>. * <math>p_i</math> die Wahrscheinlichkeit, dass genau die Eingabe <math>i</math> auftritt. * <math>t_i</math> die Anzahl der elementaren Rechenschritte (Laufzeit), die der Algorithmus für die Eingabe <math>i</math> benötigt. Häufig wird der Einfachheit halber eine '''Gleichverteilung''' (Laplace-Annahme) vorausgesetzt. Das bedeutet, man geht davon aus, dass jede mögliche Eingabekonfiguration gleich wahrscheinlich ist. === Beispiel: Average-Case der Linearen Suche === Um das Prinzip zu verdeutlichen, betrachten wir den Algorithmus der linearen Suche: Ein Array der Länge <math>n</math> wird von vorne nach hinten durchsucht, bis ein gesuchtes Element <math>x</math> gefunden wird. Wir treffen für diese Analyse folgende Annahmen: # Das gesuchte Element <math>x</math> befindet sich definitiv im Array. # Jede Position <math>1, 2, \dots, n</math> im Array ist für das Element <math>x</math> gleich wahrscheinlich. Die Wahrscheinlichkeit <math>p</math>, dass es an einer bestimmten Stelle steht, ist somit <math>p = \frac{1}{n}</math>. Wenn das Element an der ersten Stelle steht, benötigen wir 1 Vergleich. Steht es an der zweiten Stelle, benötigen wir 2 Vergleiche, und so weiter. Steht es an der letzten Stelle, benötigen wir <math>n</math> Vergleiche. Wir setzen diese Werte in die Formel für den Erwartungswert ein: <math>E(T) = \sum_{i=1}^{n} \left( \frac{1}{n} \cdot i \right)</math> Da <math>\frac{1}{n}</math> ein konstanter Faktor unabhängig vom Laufindex <math>i</math> ist, können wir ihn vor die Summe ziehen: <math>E(T) = \frac{1}{n} \cdot \sum_{i=1}^{n} i</math> Der hintere Teil der Gleichung ist die bekannte '''Gaußsche Summenformel''' (arithmetische Reihe), die sich auflösen lässt zu <math>\frac{n(n+1)}{2}</math>. Wir setzen dies ein: <math>E(T) = \frac{1}{n} \cdot \frac{n(n+1)}{2}</math> Durch Kürzen des <math>n</math> erhalten wir das finale Ergebnis: <math>E(T) = \frac{n+1}{2} = \frac{1}{2}n + \frac{1}{2}</math> '''Fazit:''' Im Durchschnitt benötigt die lineare Suche <math>\frac{n+1}{2}</math> Vergleiche. Für die asymptotische Laufzeitanalyse ignorieren wir Konstanten und niederwertige Terme, sodass auch der Average-Case der linearen Suche in der Komplexitätsklasse <math>\mathcal{O}(n)</math> liegt. === Indikatorvariablen und die Harmonische Reihe === Bei einfachen Algorithmen reicht eine Gleichverteilung zur Herleitung oft aus. Bei komplexeren, teile-und-herrsche-basierten Algorithmen wie [[Quicksort]] reicht dies nicht mehr. Um den Average-Case von Quicksort (<math>\mathcal{O}(n \log n)</math>) selbstständig ermitteln zu können, benötigt man zwei mathematische Werkzeuge: '''Indikatorzufallsvariablen''' und die '''Harmonische Reihe'''. Um diese Konzepte zu erlernen, betrachten wir als vorbereitendes Beispiel die Bestimmung des Maximums in einem unsortierten Array: <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> Die grundlegenden Vergleiche (<code>A[i] > max</code>) finden in jedem Fall <math>n-1</math> Mal statt. Die spannende Frage für die Laufzeitanalyse (insbesondere beim Schreiben in den Speicher) ist jedoch: '''Wie oft wird die Update-Operation <code>max = A[i]</code> im Durchschnitt ausgeführt?''' Wir gehen von einer zufälligen Permutation (Anordnung) der Zahlen aus. * '''Schritt 1: Indikatorvariablen definieren''' Wir definieren eine Indikatorzufallsvariable <math>X_i</math>. Diese nimmt den Wert <math>1</math> an, wenn an der Stelle <math>i</math> ein neues Maximum gefunden wird, und <math>0</math>, wenn nicht. Die Gesamtzahl der Updates <math>X</math> ist die Summe aller <math>X_i</math>: <math>X = \sum_{i=1}^{n} X_i</math>. * '''Schritt 2: Wahrscheinlichkeit ermitteln''' Damit an der Stelle <math>i</math> ein neues Maximum gefunden wird, muss die Zahl <math>A[i]</math> die größte unter den ersten <math>i</math> Zahlen sein. Da wir von einer zufälligen Anordnung ausgehen, ist jede der ersten <math>i</math> Zahlen mit gleicher Wahrscheinlichkeit die größte. Die Wahrscheinlichkeit ist also: <math>P(X_i = 1) = \frac{1}{i}</math> Der Erwartungswert <math>E[X_i]</math> ist bei Indikatorvariablen identisch mit ihrer Wahrscheinlichkeit: <math>E[X_i] = \frac{1}{i}</math>. * '''Schritt 3: Erwartungswert der Summe berechnen''' Dank der Linearität des Erwartungswertes (Erwartungswerte von Summen dürfen als Summe der Erwartungswerte geschrieben werden) erhalten wir: <math>E[X] = E\left[\sum_{i=1}^{n} X_i\right] = \sum_{i=1}^{n} E[X_i] = \sum_{i=1}^{n} \frac{1}{i} = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}</math> Diese Summe ist in der Mathematik als die <math>n</math>-te Partialsumme der '''Harmonischen Reihe''' (<math>H_n</math>) bekannt. Für große <math>n</math> wächst die harmonische Reihe logarithmisch, sie lässt sich annähern durch den natürlichen Logarithmus: <math>H_n \approx \ln(n)</math>. '''Erkenntnis für Quicksort:''' Die Update-Operation wird im Average-Case also nur <math>\mathcal{O}(\log n)</math> Mal ausgeführt, obwohl das Array <math>n</math> Elemente hat. Genau dieses Prinzip – das Aufsummieren von stochastischen Wahrscheinlichkeiten der einzelnen Array-Elemente, die zu einer harmonischen Reihe und damit zu einem logarithmischen Faktor führen – ist der mathematische Schlüssel, um die Average-Case-Laufzeit von <math>\mathcal{O}(n \log n)</math> bei Quicksort herzuleiten. == Beispiel: Laufzeitanalyse von Insertion Sort == Im Folgenden wird die Laufzeitanalyse beispielhaft anhand des [[Insertion-sort|Insertion Sorts]] (Sortieren durch Einfügen) durchgeführt. Wir betrachten eine mögliche Implementierung in der Programmiersprache [[Java]]. Der Algorithmus arbeitet mit einem [[Array]] als Datenstruktur und verwendet als [[Kontrollstruktur|Kontrollstrukturen]] [[Verzweigung|Verzweigungen]] und [[Schleife|Schleifen]]. <syntaxhighlight lang="java"> public void sortierenEinfuegen_MC() { int v, i, j; for (i = 1; i < zSortfeld.length; i++) { c++; // Zähler für Vergleiche if (zSortfeld[i] < zSortfeld[i - 1]) { v = zSortfeld[i]; j = i; do { zSortfeld[j] = zSortfeld[j - 1]; j--; } while ((j > 0) && (zSortfeld[j - 1] > v)); zSortfeld[j] = v; } printAnalyse(i); } } </syntaxhighlight> Wir analysieren nun die drei Szenarien für eine Liste mit <math>n</math> Elementen und betrachten zunächst den Zeitverbrauch für die durchzuführenden Vergleichsoperationen. Den konstanten Zeitverbrauch für einen einzelnen Vergleich bezeichnen wir allgemein mit <math>c</math>. === 1. Best-Case-Szenario (Bester Fall) === Ein Best-Case-Szenario liegt vor, wenn die Liste bereits aufsteigend sortiert ist, beispielsweise: <code>[0, 2, 3, 5, 7, 11]</code> * '''Verhalten:''' Die äußere <code>for</code>-Schleife durchläuft das Array <math>n - 1</math> Mal. Da das aktuell betrachtete Element stets größer oder gleich seinem Vorgänger ist, ist die Bedingung der <code>if</code>-Anweisung (<code>zSortfeld[i] < zSortfeld[i - 1]</code>) '''immer falsch'''. Die innere <code>do-while</code>-Schleife wird somit nie betreten. * '''Aufwand:''' Es findet pro Durchlauf der äußeren Schleife exakt ein Vergleich statt. Der Gesamtaufwand lautet <math>c \cdot (n - 1)</math>. * '''Komplexität:''' Für sehr große <math>n</math> wächst der Aufwand linear zur Eingabemenge. Der Insertion Sort hat im Best-Case somit eine Zeitkomplexität von <math>\mathcal{O}(n)</math>. === 2. Worst-Case-Szenario (Schlechtester Fall) === Ein Worst-Case-Szenario liegt vor, wenn die Liste in genau umgekehrter (absteigender) Reihenfolge vorliegt, beispielsweise: <code>[11, 7, 5, 3, 2, 0]</code> * '''Verhalten:''' Die <code>if</code>-Bedingung ist hier '''immer wahr'''. Das aktuell betrachtete Element muss in der inneren <code>do-while</code>-Schleife jedes Mal bis ganz an den Anfang des Arrays verschoben werden. * '''Aufwand:''' ** Beim ersten Durchlauf vergleichen wir nur die 7 mit der 11 (1 Vergleich). Aufwand: <math>c \cdot 1</math>. ** Beim zweiten Durchlauf müssen wir das nächste Element mit den zwei bereits sortierten vergleichen. Aufwand: <math>c \cdot 2</math>. ** Dies setzt sich fort bis zum letzten Durchlauf, der <math>n - 1</math> Vergleiche erfordert. Aufwand: <math>c \cdot (n - 1)</math>. Der Gesamtaufwand für die Vergleiche entspricht einer [[Arithmetische-reihe|arithmetischen Reihe]] (Gaußsche Summenformel): <math>c \cdot (1 + 2 + 3 + \dots + (n - 1)) = c \cdot \frac{(n - 1) \cdot n}{2} = \frac{c}{2}n^2 - \frac{c}{2}n</math> [[Datei:Asymptote an quadratische Funktion2.png|mini|Quadratisches Wachstum]] Für die asymptotische Betrachtung extrem großer Werte von <math>n</math> verwerfen wir den langsamer wachsenden (niederwertigen) Term <math>\frac{c}{2}n</math> sowie die Konstante <math>\frac{c}{2}</math>. * '''Komplexität:''' Der Aufwand wächst quadratisch. Der Insertion Sort hat im Worst-Case somit eine Zeitkomplexität von <math>\mathcal{O}(n^2)</math>. === 3. Average-Case-Szenario (Durchschnittlicher Fall) === Das Average-Case-Szenario geht von einer völlig zufälligen Verteilung der Werte im Array aus. * '''Verhalten:''' Im Durchschnitt ist das betrachtete Element kleiner als die Hälfte der bereits sortierten Elemente. Die innere Schleife muss das Element also nicht bis ganz an den Anfang, sondern im Mittel nur bis in die Mitte des bisher sortierten Teilbereichs verschieben. * '''Aufwand:''' Die Anzahl der Vergleiche und Verschiebungen halbiert sich im Vergleich zum Worst-Case in etwa. Der rechnerische Aufwand läge grob bei <math>\frac{1}{2} \cdot \frac{c}{2}n^2</math>. * '''Komplexität:''' Da in der asymptotischen Landau-Notation konstante Faktoren (wie die Halbierung) ignoriert werden, da primär die höchste Potenz das Wachstum dominiert, bleibt es auch hier bei einem quadratischen Wachstum. Die Zeitkomplexität im Average-Case lautet ebenfalls <math>\mathcal{O}(n^2)</math>. === Einfluss weiterer Operationen === Wie beeinflussen Lese- und Schreiboperationen (das tatsächliche Verschieben der Werte im Array) die Zeitkomplexität? Für das Verschieben käme lediglich ein konstanter Aufwand je Vergleich hinzu. Nennen wir diesen Aufwand <math>v</math>. Die angepasste Worst-Case-Funktion lautet dann beispielsweise: <math>\frac{v+c}{2}n^2 - \frac{v+c}{2}n</math> Auch hier gilt: Für sehr große <math>n</math> werden der niederwertige Term und die konstanten Faktoren ignoriert. Es bleibt bei der Erkenntnis, dass Lese- und Schreibzugriffe die fundamentale Komplexitätsklasse nicht verändern. Das Laufzeitverhalten bleibt asymptotisch in der Klasse <math>\mathcal{O}(n^2)</math>. [[Kategorie:Programmierung]] [[Kategorie:AHR_I_Informatik_LK]]

Laufzeitanalyse

2026-04-20T07:16:21Z

Flbkwikiadmin:

== Einführung ==
[[Datei:Laufzeitanalyse asymptotisch.png|mini|Asymptotische Annäherung einer Funktion]]
[[Datei:Asymptote an quadratische Funktion2.png|mini|Quadratisches Wachstum]]
Die '''Laufzeitanalyse''' untersucht, wie viele Rechenschritte ein [[Algorithmus]] benötigt, um ein Problem zu lösen.

Da die tatsächliche Laufzeit eines Programms stark vom Computer abhängt (z. B. Prozessor oder Arbeitsspeicher), betrachtet man nicht die Zeit in Sekunden, sondern die Anzahl der benötigten '''Operationen'''.

Diese Anzahl hängt von der Größe der Eingabe ab.
Die Eingabegröße wird meist mit <math>n</math> bezeichnet.

Beispiel:
* Beim Sortieren ist <math>n</math> die Anzahl der zu sortierenden Werte.
* Beim Durchsuchen einer Liste ist <math>n</math> die Länge der Liste.

Für kleine Eingaben spielt die Laufzeitanalyse oft kaum eine Rolle, weil selbst langsame Verfahren schnell genug sind.
Wichtig wird sie bei großen Datenmengen.

Die Frage lautet dann:

'''Wie wächst der Aufwand, wenn die Eingabe immer größer wird?'''

Genau das beschreibt die '''asymptotische Laufzeit'''.

Wenn sich die Laufzeit eines Algorithmus durch eine Funktion beschreiben lässt, z. B.

<math>f(x)=\frac{1}{x}+x</math>

dann erkennt man für große <math>x</math>, dass der Anteil <math>\frac{1}{x}</math> immer kleiner wird.
Das Verhalten der Funktion wird dann fast nur noch durch <math>x</math> bestimmt.

Deshalb betrachtet man bei der Laufzeitanalyse nur das Verhalten für große Werte von <math>n</math>.
Dieses Verhalten beschreibt man mit der '''Landau-Notation''' (Groß-O-Notation), z. B.:

<math>\mathcal{O}(n)</math>, <math>\mathcal{O}(n^2)</math>, <math>\mathcal{O}(n \log n)</math>

Damit kann man Algorithmen vergleichen, ohne von einer bestimmten Hardware abhängig zu sein.

=== Wichtige Abgrenzung ===
Die asymptotische Laufzeitanalyse gibt '''nicht''' an, wie viele Sekunden ein Programm wirklich benötigt.

Sie beschreibt nur, '''wie stark der Aufwand wächst''', wenn die Eingabemenge größer wird.
Das macht verschiedene Algorithmen vergleichbar.

== Szenarien der Laufzeitabschätzung ==

Bei der Laufzeitanalyse betrachtet man meist drei Fälle:

* '''Best Case''' (bester Fall):
Der Algorithmus arbeitet unter idealen Bedingungen und benötigt minimalen Aufwand.

* '''Worst Case''' (schlechtester Fall):
Der Algorithmus trifft auf die ungünstigste Eingabe und benötigt maximalen Aufwand.

* '''Average Case''' (durchschnittlicher Fall):
Man betrachtet den durchschnittlichen Aufwand bei zufälligen Eingaben.

Diese drei Fälle helfen dabei, das Verhalten eines Algorithmus besser einzuschätzen.

== Average-Case und Erwartungswert ==

Der Average-Case beschreibt die '''durchschnittliche Laufzeit'''.

Mathematisch wird diese mit dem '''Erwartungswert''' berechnet:

<math>E(T)=\sum_{i=1}^{|E|} p_i \cdot t_i</math>

Dabei gilt:

* <math>t_i</math>: Laufzeit bei einer bestimmten Eingabe
* <math>p_i</math>: Wahrscheinlichkeit dieser Eingabe

Der Erwartungswert ist also:

'''Laufzeit × Wahrscheinlichkeit'''

für alle möglichen Eingaben zusammengezählt.

Oft nimmt man an, dass alle Eingaben gleich wahrscheinlich sind.
Dann spricht man von einer '''Gleichverteilung'''.

---

=== Beispiel: Lineare Suche ===

Bei der linearen Suche wird eine Liste von vorne nach hinten durchsucht.

Steht das gesuchte Element:

* an Position 1 → 1 Vergleich
* an Position 2 → 2 Vergleiche
* ...
* an Position <math>n</math> → <math>n</math> Vergleiche

Wenn jede Position gleich wahrscheinlich ist, ergibt sich:

<math>E(T)=\frac{1}{n}\sum_{i=1}^{n} i</math>

Mit der Gaußschen Summenformel:

<math>\sum_{i=1}^{n} i = \frac{n(n+1)}{2}</math>

folgt:

<math>E(T)=\frac{1}{n}\cdot\frac{n(n+1)}{2}=\frac{n+1}{2}</math>

Im Durchschnitt benötigt die lineare Suche also etwa halb so viele Vergleiche wie im schlechtesten Fall.

Für große <math>n</math> dominiert der Term <math>n</math>, daher gilt:

<math>\mathcal{O}(n)</math>

== Beispiel: Laufzeitanalyse von Insertion Sort ==

Beim [[Insertion-sort|Insertion Sort]] wird jedes neue Element an der richtigen Stelle in den bereits sortierten Teil eingefügt.

=== Best Case ===

Der beste Fall liegt vor, wenn die Liste bereits sortiert ist:

<code>[1,2,3,4,5]</code>

Dann genügt pro Element ein Vergleich.

Bei <math>n</math> Elementen:

<math>T(n)=n-1</math>

Das Wachstum ist linear:

<math>\mathcal{O}(n)</math>

=== Worst Case ===

Der schlechteste Fall liegt vor, wenn die Liste rückwärts sortiert ist:

<code>[5,4,3,2,1]</code>

Dann muss jedes neue Element an den Anfang verschoben werden.

Die Anzahl der Vergleiche ist:

<math>1+2+3+\dots+(n-1)</math>

Mit Gauß:

<math>\frac{n(n-1)}{2}</math>

Das ergibt quadratisches Wachstum:

<math>\mathcal{O}(n^2)</math>

=== Average Case ===

Bei zufälliger Reihenfolge liegt das neue Element im Durchschnitt ungefähr in der Mitte des bereits sortierten Bereichs.

Daher braucht man im Mittel etwa halb so viele Vergleiche wie im Worst Case:

<math>\frac{1}{2}\cdot\frac{n(n-1)}{2}</math>

Das ist ebenfalls proportional zu <math>n^2</math>.

Deshalb gilt auch hier:

<math>\mathcal{O}(n^2)</math>

Der konstante Faktor ist zwar kleiner als im Worst Case, die '''Komplexitätsklasse''' bleibt aber gleich.

== Wichtige Erkenntnis ==

Bei der Groß-O-Notation interessieren nur:

* das grundsätzliche Wachstum,
* die höchste Potenz.

Konstanten werden ignoriert.

Beispiele:

* <math>3n</math> → <math>\mathcal{O}(n)</math>
* <math>\frac{1}{2}n^2</math> → <math>\mathcal{O}(n^2)</math>

Deshalb können zwei Algorithmen unterschiedlich schnell sein, aber trotzdem dieselbe Komplexitätsklasse besitzen.

[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]

Laufzeitanalyse

2026-04-20T07:15:31Z

Flbkwikiadmin:

== Einführung ==
[[Datei:Laufzeitanalyse asymptotisch.png|mini|Asymptotische Annäherung einer Funktion]]

Die '''Laufzeitanalyse''' untersucht, wie viele Rechenschritte ein [[Algorithmus]] benötigt, um ein Problem zu lösen.

Da die tatsächliche Laufzeit eines Programms stark vom Computer abhängt (z. B. Prozessor oder Arbeitsspeicher), betrachtet man nicht die Zeit in Sekunden, sondern die Anzahl der benötigten '''Operationen'''.

Diese Anzahl hängt von der Größe der Eingabe ab.
Die Eingabegröße wird meist mit <math>n</math> bezeichnet.

Beispiel:
* Beim Sortieren ist <math>n</math> die Anzahl der zu sortierenden Werte.
* Beim Durchsuchen einer Liste ist <math>n</math> die Länge der Liste.

Für kleine Eingaben spielt die Laufzeitanalyse oft kaum eine Rolle, weil selbst langsame Verfahren schnell genug sind.
Wichtig wird sie bei großen Datenmengen.

Die Frage lautet dann:

'''Wie wächst der Aufwand, wenn die Eingabe immer größer wird?'''

Genau das beschreibt die '''asymptotische Laufzeit'''.

Wenn sich die Laufzeit eines Algorithmus durch eine Funktion beschreiben lässt, z. B.

<math>f(x)=\frac{1}{x}+x</math>

dann erkennt man für große <math>x</math>, dass der Anteil <math>\frac{1}{x}</math> immer kleiner wird.
Das Verhalten der Funktion wird dann fast nur noch durch <math>x</math> bestimmt.

Deshalb betrachtet man bei der Laufzeitanalyse nur das Verhalten für große Werte von <math>n</math>.
Dieses Verhalten beschreibt man mit der '''Landau-Notation''' (Groß-O-Notation), z. B.:

<math>\mathcal{O}(n)</math>, <math>\mathcal{O}(n^2)</math>, <math>\mathcal{O}(n \log n)</math>

Damit kann man Algorithmen vergleichen, ohne von einer bestimmten Hardware abhängig zu sein.

=== Wichtige Abgrenzung ===
Die asymptotische Laufzeitanalyse gibt '''nicht''' an, wie viele Sekunden ein Programm wirklich benötigt.

Sie beschreibt nur, '''wie stark der Aufwand wächst''', wenn die Eingabemenge größer wird.
Das macht verschiedene Algorithmen vergleichbar.

== Szenarien der Laufzeitabschätzung ==

Bei der Laufzeitanalyse betrachtet man meist drei Fälle:

* '''Best Case''' (bester Fall):
Der Algorithmus arbeitet unter idealen Bedingungen und benötigt minimalen Aufwand.

* '''Worst Case''' (schlechtester Fall):
Der Algorithmus trifft auf die ungünstigste Eingabe und benötigt maximalen Aufwand.

* '''Average Case''' (durchschnittlicher Fall):
Man betrachtet den durchschnittlichen Aufwand bei zufälligen Eingaben.

Diese drei Fälle helfen dabei, das Verhalten eines Algorithmus besser einzuschätzen.

== Average-Case und Erwartungswert ==

Der Average-Case beschreibt die '''durchschnittliche Laufzeit'''.

Mathematisch wird diese mit dem '''Erwartungswert''' berechnet:

<math>E(T)=\sum_{i=1}^{|E|} p_i \cdot t_i</math>

Dabei gilt:

* <math>t_i</math>: Laufzeit bei einer bestimmten Eingabe
* <math>p_i</math>: Wahrscheinlichkeit dieser Eingabe

Der Erwartungswert ist also:

'''Laufzeit × Wahrscheinlichkeit'''

für alle möglichen Eingaben zusammengezählt.

Oft nimmt man an, dass alle Eingaben gleich wahrscheinlich sind.
Dann spricht man von einer '''Gleichverteilung'''.

---

=== Beispiel: Lineare Suche ===

Bei der linearen Suche wird eine Liste von vorne nach hinten durchsucht.

Steht das gesuchte Element:

* an Position 1 → 1 Vergleich
* an Position 2 → 2 Vergleiche
* ...
* an Position <math>n</math> → <math>n</math> Vergleiche

Wenn jede Position gleich wahrscheinlich ist, ergibt sich:

<math>E(T)=\frac{1}{n}\sum_{i=1}^{n} i</math>

Mit der Gaußschen Summenformel:

<math>\sum_{i=1}^{n} i = \frac{n(n+1)}{2}</math>

folgt:

<math>E(T)=\frac{1}{n}\cdot\frac{n(n+1)}{2}=\frac{n+1}{2}</math>

Im Durchschnitt benötigt die lineare Suche also etwa halb so viele Vergleiche wie im schlechtesten Fall.

Für große <math>n</math> dominiert der Term <math>n</math>, daher gilt:

<math>\mathcal{O}(n)</math>

== Beispiel: Laufzeitanalyse von Insertion Sort ==

Beim [[Insertion-sort|Insertion Sort]] wird jedes neue Element an der richtigen Stelle in den bereits sortierten Teil eingefügt.

=== Best Case ===

Der beste Fall liegt vor, wenn die Liste bereits sortiert ist:

<code>[1,2,3,4,5]</code>

Dann genügt pro Element ein Vergleich.

Bei <math>n</math> Elementen:

<math>T(n)=n-1</math>

Das Wachstum ist linear:

<math>\mathcal{O}(n)</math>

=== Worst Case ===

Der schlechteste Fall liegt vor, wenn die Liste rückwärts sortiert ist:

<code>[5,4,3,2,1]</code>

Dann muss jedes neue Element an den Anfang verschoben werden.

Die Anzahl der Vergleiche ist:

<math>1+2+3+\dots+(n-1)</math>

Mit Gauß:

<math>\frac{n(n-1)}{2}</math>

Das ergibt quadratisches Wachstum:

<math>\mathcal{O}(n^2)</math>

=== Average Case ===

Bei zufälliger Reihenfolge liegt das neue Element im Durchschnitt ungefähr in der Mitte des bereits sortierten Bereichs.

Daher braucht man im Mittel etwa halb so viele Vergleiche wie im Worst Case:

<math>\frac{1}{2}\cdot\frac{n(n-1)}{2}</math>

Das ist ebenfalls proportional zu <math>n^2</math>.

Deshalb gilt auch hier:

<math>\mathcal{O}(n^2)</math>

Der konstante Faktor ist zwar kleiner als im Worst Case, die '''Komplexitätsklasse''' bleibt aber gleich.

== Wichtige Erkenntnis ==

Bei der Groß-O-Notation interessieren nur:

* das grundsätzliche Wachstum,
* die höchste Potenz.

Konstanten werden ignoriert.

Beispiele:

* <math>3n</math> → <math>\mathcal{O}(n)</math>
* <math>\frac{1}{2}n^2</math> → <math>\mathcal{O}(n^2)</math>

Deshalb können zwei Algorithmen unterschiedlich schnell sein, aber trotzdem dieselbe Komplexitätsklasse besitzen.

[[Kategorie:Programmierung]]
[[Kategorie:AHR_I_Informatik_LK]]

Laufzeitanalyse

2026-04-20T06:45:57Z

2026-04-16T12:27:35Z

Flbkwikiadmin: Die Seite wurde neu angelegt: „== Einführung == '''Funktionale Abhängigkeiten''' bilden die Grundlage für die Normalisierung von Relationenschemata und die Bestimmung von Primärschlüsseln. Relationen werden durch Attribute definiert. Bestimmen einige dieser Attribute eindeutig die Werte anderer Attribute, so spricht man von funktionaler Abhängigkeit. == Funktionale Abhängigkeit == Betrachtet man folgende Relation, wird man festste…“

== Einführung ==
'''Funktionale Abhängigkeiten''' bilden die Grundlage für die [[Normalisierung]] von Relationenschemata und die Bestimmung von [[Primärschlüssel]]n. [[Relation (Datenbanken)|Relationen]] werden durch [[Attribut|Attribute]] definiert. Bestimmen einige dieser Attribute eindeutig die Werte anderer Attribute, so spricht man von funktionaler Abhängigkeit.

== Funktionale Abhängigkeit ==
Betrachtet man folgende Relation, wird man feststellen, dass die Attribute ''Nachname'' und ''Vorname'' abhängig sind von der ''IdMitarbeiter''. Man sagt in diesem Zusammenhang, die Attribute Nachname und Vorname sind funktional abhängig von der IdMitarbeiter.

{| class="wikitable"
! IdMitarbeiter !! Nachname !! Vorname
|-
| 1 || Krause || Sabine
|-
| 2 || Schrotter || Claudia
|-
| 3 || Hermann || Markus
|-
| 4 || Krause || Christoph
|-
| 5 || Bitter || Manuel
|-
| 6 || Schulze || Claudia
|}

Wenn man also die `IdMitarbeiter` kennt, kann man auch den Namen des Mitarbeiters benennen. Andersherum ist der Schluss nicht möglich: Ist der Nachname bekannt (z. B. Krause), lässt sich die `IdMitarbeiter` nicht eindeutig bestimmen.

In Anlehnung an die Mathematik wird hier von der funktionalen Abhängigkeit gesprochen, da eine mathematische Funktion immer den gleichen Ausgabewert bei gleichen Eingabewerten liefert. Die Funktion \({ y = 3 \cdot x }\) liefert für \({ x = 4 }\) immer die Ausgabe \(12\) für die Variable \(y\). Für jede beliebige Zahl, die man für die Variable \(x\) einsetzt, ergibt sich also ein ganz bestimmter Wert für \(y\). Man kann sagen, dass der Wert \(y\) abhängig ist vom Wert \(x\) bzw. \(x\) bestimmt \(y\).

Mathematisch spricht man auch von einer '''Determinante''' und schreibt:
\({ x \rightarrow y }\)

Analog schreibt man also für die besprochene funktionale Abhängigkeit der Attribute:
\({ \text{IdMitarbeiter} \rightarrow \text{Nachname}, \text{Vorname} }\)

> '''Wichtig:''' Die funktionale Abhängigkeit muss für alle möglichen bzw. denkbaren Tupel (Datensätze) einer Relation gelten.

== Volle funktionale Abhängigkeit ==
Man spricht von '''voller funktionaler Abhängigkeit''', wenn jedes Nichtschlüssel-Attribut nur durch den ''gesamten'' Primärschlüssel eindeutig bestimmt werden kann.

Nehmen wir an, der zusammengesetzte Primärschlüssel der obigen Relation würde sich aus den Attributen `IdMitarbeiter` und `Nachname` zusammensetzen. Es gälte also:
\({ (\text{IdMitarbeiter}, \text{Nachname}) \rightarrow \text{Vorname} }\)
(Vorname ist funktional von IdMitarbeiter und Nachname abhängig.)

Allerdings ist der Vorname nicht vom Nachnamen funktional abhängig. Der Vorname „Claudia“ gilt sowohl für Schulze als auch für Schrotter. Das Attribut `IdMitarbeiter` bestimmt aber nach wie vor alleine und eindeutig das Attribut `Vorname`. Auf das Attribut `Nachname` kann also im Schlüssel verzichtet werden.

Da das Nichtschlüssel-Attribut `Vorname` auch durch einen Teil des Primärschlüssels – nämlich `IdMitarbeiter` – bestimmbar ist, ist `Vorname` '''nicht voll funktional abhängig''' von der Kombination aus IdMitarbeiter und Nachname. Die volle funktionale Abhängigkeit würde hier nur für das isolierte Attribut `IdMitarbeiter` gelten.

== Transitive Abhängigkeit ==
Angenommen, wir haben eine Relation \(R\) mit den Attributen \(A\), \(B\) und \(C\).
* \(A\) ist der Primärschlüssel.
* \(A\) bestimmt \(B\) (\({ A \rightarrow B }\)).
* \(B\) ist nicht Teil des Primärschlüssels.
* Dennoch gilt \({ B \rightarrow C }\).

Somit ist \(C\) '''transitiv''' von \(A\) abhängig.

'''Beispiel aus der Praxis:'''
Mit Hilfe des Primärschlüssels `IdMitarbeiter` lässt sich eindeutig der Salon bestimmen, in dem der Mitarbeiter arbeitet. Allerdings hängt der Salonname funktional von der `IdSalon` ab und somit nur ''transitiv'' von der `IdMitarbeiter`.

Um ein solches Schema in die [[Normalisierung#Die_3._Normalform_(3NF)|3. Normalform (3NF)]] zu überführen, müssen die Saloninformationen in eine eigene Relation ausgelagert werden.

[[Kategorie:Datenbanken]]
[[Kategorie:FI_I_SDM]]