Warum Sortieren? Grundlagen & Komplexität

Gegeben ist eine Folge von $n$ Elementen. Gesucht ist eine Anordnung, in der die Elemente aufsteigend (oder absteigend) sortiert sind.

Vergleichsbasierte Verfahren dürfen nur eine Operation nutzen: den Vergleich zweier Elemente. Daraus folgt eine wichtige untere Schranke: Kein vergleichsbasiertes Verfahren kann schneller sein als $O(n \log n)$ im Worst Case.

Bubble Sort läuft wiederholt durch die Liste und vertauscht benachbarte Elemente, wenn sie in der falschen Reihenfolge stehen. Große Elemente „blubbern" so ans Ende.

Fall	Laufzeit
Best Case (schon sortiert)	$O(n)$
Average Case	$O(n^2)$
Worst Case (umgekehrt sortiert)	$O(n^2)$

Die quadratische Laufzeit entsteht, weil im schlimmsten Fall jeder der $n$ Durchläufe bis zu $n-1$ Vergleiche braucht:

$\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} \in O(n^2)$