Sortieren

In diesem Kapitel werden zahlreiche Algorithmen zum Sortieren vorgestellt. Die Verfahren eignen sich gut, um grundsätzliche Programmierstrategien wie Greedy, Divide & Conquer und Rekursion zu behandeln. Eine Greedy-Strategie versucht durch gieriges Vorgehen das jeweils kurzfristig bestmögliche zu erreichen. Bei Divide & Conquer wird zunächst das gegebene Problem in Teilprobleme zerlegt, dann deren Lösungen errechnet und diese dann anschließend zur Gesamtlösung zusammengeführt. Rekursive Verfahren lösen die ursprüngliche Aufgabenstellung auf einer reduzierten Problemgröße mit demselben Lösungsansatz und konstruieren aus dieser Teillösung die Gesamtlösung.

Motivation für Sortieren:

1. Häufiges Suchen
   Einmal sortieren, dann jeweils $\log n$ Aufwand.
2. Tritt ein Element in zwei Listen $L_{1}, L_{2}$ auf?
   Sortiere $L_{1} \cdot L_{2}$, dann nach Doppelten suchen!