WhatsApp Image 2025-02-25 at 11.50.50 AM.jpeg

## Algorithmen und Datenstrukturen ### Sortieren #### Grundlagen * **Eingabe:** Folge von n Elementen $\langle a_1, a_2,..., a_n \rangle$ * **Ausgabe:** Permutation $\langle a_1', a_2',..., a_n' \rangle$ der Eingabefolge, sodass $a_1' \leq a_2' \leq... \leq a_n'$ gilt. * **Sortieralgorithmu...

## Algorithmen und Datenstrukturen ### Sortieren #### Grundlagen * **Eingabe:** Folge von n Elementen $\langle a_1, a_2,..., a_n \rangle$ * **Ausgabe:** Permutation $\langle a_1', a_2',..., a_n' \rangle$ der Eingabefolge, sodass $a_1' \leq a_2' \leq... \leq a_n'$ gilt. * **Sortieralgorithmus heißt korrekt,** falls er für jede Eingabe eine korrekte Ausgabe liefert. * **In-place-Sortieralgorithmus:** Benötigt zusätzlich zum Eingabefeld nur konstant viel Speicher. * **Stabiler Sortieralgorithmus:** Behält die relative Reihenfolge von Elementen mit gleichem Schlüssel bei. #### Notation * n: Anzahl der Elemente * A: Eingabefeld * i, j, k: Indizes * key: Schlüssel des Elements * Laufzeit im schlechtesten Fall: O(n^2) * Laufzeit im besten Fall: $\Omega(n)$ * In-place: Ja * Stabil: Ja #### Einfache Sortierverfahren ##### Insertionsort (Sortieren durch Einfügen) * Idee: Durchlaufe das Feld von links nach rechts. Füge jedes Element an der richtigen Stelle in den bereits sortierten Teil des Feldes ein. ``` for j = 2 to A.length key = A[j] i = j - 1 while i > 0 und A[i] > key A[i + 1] = A[i] i = i - 1 A[i + 1] = key ``` ##### Selectionsort (Sortieren durch Auswählen) * Idee: Finde das kleinste Element im unsortierten Teil des Feldes und tausche es mit dem ersten Element des unsortierten Teils. ``` for i = 1 to A.length - 1 min_index = i for j = i + 1 to A.length if A[j] < A[min_index] min_index = j swap A[i] und A[min_index] ``` * Laufzeit: O(n^2) * In-place: Ja * Stabil: Nein ##### Bubblesort (Sortieren durch Aufsteigen) * Idee: Durchlaufe das Feld mehrfach. Vergleiche jeweils zwei benachbarte Elemente und vertausche sie, falls sie in der falschen Reihenfolge sind. ``` for i = 1 to A.length - 1 for j = A.length downto i + 1 if A[j] < A[j - 1] swap A[j] und A[j - 1] ``` * Laufzeit: O(n^2) * In-place: Ja * Stabil: Ja #### Divide-and-Conquer-Verfahren ##### Mergesort (Sortieren durch Mischen) * Idee: Teile das Feld in zwei Hälften, sortiere jede Hälfte rekursiv und mische die beiden sortierten Hälften. ``` mergesort(A, p, r) if p < r q = (p + r) / 2 mergesort(A, p, q) mergesort(A, q + 1, r) merge(A, p, q, r) ``` ``` merge(A, p, q, r) n1 = q - p + 1 n2 = r - q let L[1..n1 + 1] und R[1..n2 + 1] neue Felder sein for i = 1 to n1 L[i] = A[p + i - 1] for j = 1 to n2 R[j] = A[q + j] L[n1 + 1] = ∞ R[n2 + 1] = ∞ i = 1 j = 1 for k = p to r if L[i]