Divide and Conquer

Question 1

Divide-and-Conquer:

Answer 1

Teile ein Problem in Teilprobleme auf. Löse
jedes Teilproblem unabhängig und kombiniere die Lösung fur die Teilprobleme zu einer Lösung fur das ursprüngliche Problem.

• Teile Problem in mehrere Teile auf (meistens zwei).
• Löse jeden Teil rekursiv.
• Fasse Lösungen der Subprobleme zu einer Gesamtlösung zusammen.

Question 2

Mergesort:

Answer 2

• Teile Array in zwei Hälften.
• Sortiere jede Hälfte rekursiv.

*Verschmelze zwei Hälften zu einem
sortierten Ganzen.

Question 3

Quicksort

Answer 3

Teile: Wähle
Pivotelement“ x aus Folge A,
z.B. das an der letzten Stelle stehende Element.
Teile A ohne x so in zwei Teilfolgen A1 und A2, dass gilt:
A1 enth¨alt nur Elemente ≤ x.
A2 enth¨alt nur Elemente ≥ x.
Herrsche:
Rekursiver Aufruf fur ¨ A1.
Rekursiver Aufruf fur ¨ A2.
Kombiniere: Bilde A durch Hintereinanderfugen von ¨ A1, x, A2