received_1000459452081181.jpeg

## Algorithmen und Datenstrukturen ### Sortieren #### Einführung * **Sortieralgorithmen** bringen eine Menge von Elementen in eine bestimmte **Ordnung**. * Die Ordnung basiert auf einer **totalen Ordnungrelation** $\le$ zwischen den Elementen. * **Beispiele:** * Zahlen aufsteigend sor...

## Algorithmen und Datenstrukturen ### Sortieren #### Einführung * **Sortieralgorithmen** bringen eine Menge von Elementen in eine bestimmte **Ordnung**. * Die Ordnung basiert auf einer **totalen Ordnungrelation** $\le$ zwischen den Elementen. * **Beispiele:** * Zahlen aufsteigend sortieren. * Namen alphabetisch sortieren. * **Ziele:** * Einfache Algorithmen mit wenig Code. * Effiziente Algorithmen, die schnell sortieren. * Algorithmen, die mit wenig Speicher auskommen. #### Übersicht Wir betrachten folgende Algorithmen: * **Einfache Verfahren:** * *Selection Sort*: einfach, in-place * *Insertion Sort*: einfach, in-place, stabil * *Bubble Sort*: einfach, in-place, stabil * **Effiziente Verfahren:** * *Merge Sort*: teile und herrsche, stabil * *Quick Sort*: teile und herrsche, in-place * *Heap Sort*: in-place * **Spezielle Verfahren:** * *Radix Sort*: basiert auf Ziffernvergleich, nicht vergleichsbasiert #### Bewertung * **Laufzeit:** * Anzahl der Vergleiche $\mathcal{C}(n)$ * Anzahl der Swaps $\mathcal{S}(n)$ * Im **besten Fall**, im **mittleren Fall**, im **schlechtesten Fall**. * **Speicherplatz:** * **in-place:** zusätzlicher Speicherbedarf ist konstant ( $\mathcal{O}(1)$ ) * **Stabilität:** * Bleibt die relative Reihenfolge von Elementen mit gleichem Schlüssel erhalten? * Wichtig, wenn bereits vorsortiert ist. #### Selection Sort 1. Finde das kleinste Element im unsortierten Bereich. 2. Vertausche es mit dem ersten Element des unsortierten Bereichs. 3. Der sortierte Bereich wächst um eins. **Beispiel:** `[5 2 8 1 9]` 1. Minimum ist `1`. Tausche `5` und `1`: `[1 2 8 5 9]` 2. Minimum ist `2`. Keine Änderung: `[1 2 8 5 9]` 3. Minimum ist `5`. Tausche `8` und `5`: `[1 2 5 8 9]` 4. Minimum ist `8`. Keine Änderung: `[1 2 5 8 9]` **Pseudocode:** ``` for i = 0 to n-2 do min = i for j = i+1 to n-1 do if a[j] < a[min] then min = j end end swap a[i] and a[min] end ``` **Analyse:** * $\mathcal{C}(n) = \frac{n(n-1)}{2} \in \mathcal{O}(n^2)$ * $\mathcal{S}(n) = n - 1 \in \mathcal{O}(n)$ * in-place * nicht stabil