Quelltext der Seite Divide and Conquer

''[[Divide and Conquer]]'', auch lateinisch als '''''Divide et impera''''' oder auf deutsch als '''Teile und herrsche''' bezeichnet, ist ein Prinzip, auf dem viele [[Algorithmus|Algorithmen]] basieren.

== Die Idee ==
Um ein großes Problem zu lösen,

# teilt man dieses in mehrere kleinere Teilprobleme
# löst diese Teilprobleme und
# führt die Lösungen zusammen.

== Alltagsbeispiel ==
Wenn man einen bestimmten Eintrag aus einem alphabetisch sortierten Wörterbuch heraussucht, blättert man dieses nicht von vorne nach hinten seitenweise durch. Stattdessen schlägt man es an einer Stelle auf, wo man das Wort ungefähr vermutet und grenzt damit den Suchraum weiter ein.

Wenn ich zum Beispiel in einem Englisch-Wörterbuch das Wort ''[[wikt:furze#English|furze]]'' suche, schlage ich das Buch irgendwo im ersten Viertel auf – der Buchstabe F ist der sechste von 26, also irgendwo im ersten Viertel – und lande vielleicht bei ''[[wikt:fickle#English|fickle]]''. Ich bin schon mal bei F, muss also auf einer der nächsten paar Seiten fündig werden. Ich blättere etwas weiter und lande bei ''[[wikt:great_tit#English|great tit]]'' – zu weit geblättert. Jetzt weiß ich aber ziemlich genau, in welchem Seitenbereich ich suchen muss, und kann das gewünschte Stichwort schnell finden.

== Divide-and-Conquer-Algorithmen ==

;[[Binäre Suche]]
:Durchsuche ein sortiertes Feld, indem du das mittlere Element betrachtest. Dann weißt du, in welcher Hälfte des Suchbereichs du weitersuchen musst.
;[[Mergesort]] und [[Quicksort]]
:Sortiere eine Liste, indem du sie in zwei Teillisten unterteilst, die du rekursiv sortierst und dann wieder zusammenfügst

[[Kategorie:Algorithmen]]