prev up next

Previous: Halteproblem Up: skript Next: Selection Sort

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!



Unterabschnitte
prev up next
Previous: Halteproblem Up: skript Next: Selection Sort