Teile und Herrsche 1 SS10

Autoren:

• Raffael Thomas Lang (siralang@stud.hs-zigr.de)
• Sebastian Kramer (sisekram@stud.hs-zigr.de)

Was ist überhaupt Divide and Conquer?

DaC (eng. "Divide and Conquer") auf deutsch "Teile und Herrsche" genannt und in lat. "divide et impera". Es beschreibt folgendes Vorgehen bei Problemen:

1. zerteilen des Problems in Teilprobleme (divide)
2. lösen der einzelnen Teilprobleme, mittels rekursiven Aufruf (conquer)
3. Teillösungen zusammenführen zu der Gesamtlösung (konkatenieren)

Das schnelle Sortieren

quicksort

Sortieren durch mischen

mergesort

Vergleich Quicksort und Mergesort

Übungen

Links und Quellen