Mathematik Informatik Philosophie Diverses Kontatkt FAQ
Benutzername:
Passwort:
 Home > News
Mittwoch, 26. April 2017 00:10 
Das Paradigma 'Divide and Conquer' am Beispiel des Quicksort-Algorithmus
 
Geschrieben von Alexander am Dienstag, 10. Januar 2006

Teile und herrsche (lateinisch: divide et impera) ist angeblich ein Ausspruch des französischen Königs Ludwigs XI.

'Teile und herrsche' steht für das Prinzip, die eigenen Gegner gegeneinander auszuspielen und deren Uneinigkeit zum eigenen Zwecke und Nutzen zu verwenden. Alles also nach dem Motto: Wenn zwei sich streiten freut sich der Dritte.

In der Informatik bezeichnet man eine bedeutende Problemlösungsstrategie mit dem englischen Analogon 'Divide and Conquer'. Auch hier wird (das gestellte Problem) geteilt und in gewisser Art und Weise anschließend (über das 'besiegte' Problem) geherrscht. Allerdings enden an dieser Stelle die Gemeinsamkeiten auch schon.

Das 'Divide and Conquer'-Prinzip versucht ein gestelltes Problem P der Größe n in zwei Teilprobleme P1 und P2 zu zerlegen (divide-Schritt). Diese Teilung führt man solange durch, bis die Problemlösung trivial, offensichtlich oder zumind. wesentlich vereinfacht wird. Die eigentliche Aufgabe besteht also letztlich darin, die Lösungen der Teilprobleme P1 und P2 zu einer -umfassenden- Lösung des Gesamtproblems zusammenzufassen (conquer-Schritt).

Ein Paradebeispiel für das Paradigma des 'Divide and Conquer' ist der im Durchschnitt schnellste Sortieralgorithmus überhaupt: Der Quicksort!

Das folgende Bild (Quelle: FH Flensburg) illustriert die Vorgehensweise eines Quicksorts angewendet auf eine (abbrechende) Folge aus dem Körper IF2={0,1}.
Im ersten Schritt wird die zu sortierende Folge a in zwei Teilfolgen b und c zerlegt, so dass alle Elemente der ersten Teilfolge b kleiner oder gleich allen Elementen der zweiten Teilfolge c sind (divide).


Im zweiten Schritt werden dann die beiden Teilfolgen (rekursiv) nach demselben Verfahren (conquer) sortiert. Die Gesamtlösung ergibt sich durch das Zusammensetzen (merge) der entstandenen und bereits sortierten Teilfolgen.


Kompakt bedeutet das:

 

if die Objektmenge ist klein genug
then löse das Problem direkt
else{
Divide:
Zerlege die Menge in mehrere Teilmengen (wenn möglich, gleicher Größe).

Conquer:
Löse das Problem rekursiv für jede Teilmenge.

Merge:
Berechne aus den für die Teilmengen erhaltenen Lösungen eine Lösung des Gesamtproblems.
}

Der Algorithmus

Wähle ein (beliebiges) Element aus der zu sortierenden Liste aus; dieses Element bezeichnet man auch oft als Pivotelement.
Anhand dieses Pivotelements zerlegen wir die Liste in zwei Teillisten
  • eine 'untere' Teilliste, die alle Elemente kleiner als dem Pivotelement enthält.
  • Und eine 'obere' Teilliste, die alle Elemente gleich oder größer dem Pivotelement enthält.
Eine mögliche Ausformulierung des Teilungsschrittes eines QuickSort in Prosa ist die Folgende:

Divide
Eingabe: Folge a0, ..., an-1 mit n Elementen
Ausgabe: Umordnung der Folge derart, dass alle Elemente a0, ..., aj kleiner oder gleich den Elementen ai, ..., an-1 sind (i > j)
Methode:
  1. wähle das mittlere Element der Folge als Vergleichs­element x;

    setze i = 0 und j = n-1;

    wiederhole solange i  kleiner oder gleich  

  2. suche von links das erste Element ai mit a größer oder gleich x;

    suche von rechts das erste Element aj mit aj echt kleiner x;

    falls i j

    1. vertausche ai und aj;

      setze i = i+1 und j = j-1;

 


Im Allgeimeinen sind mehrere Teilungsschritte erforderlich. Weiterhin muss man nicht das mittlere Element als Pivotelement wählen, man könnte auch das erste oder letzte Element wählen; es ist also für die Funktionalität des Quicksorts nicht relevatn, welches ausgezeichnete Element man zum Pivotelement wählt. Für die Kosten des Quicksorts (bezgl. der Laufzeit) ist es optimal das Pivotelement stets probabilistisch zu wählen.

Es sei A die zu sortierende Liste mit Integer-Werten. Obigen Algorithmus angewendet auf den Quicksort ergibt dann:

 

algorithm QuickSort (A)

if |A| = 1 then return A
else{
if alle Schlüssel in S sind gleich then 
     return A
else
Divide: Wähle x := aj.key, so dass x nicht minimal ist in A. Berechne eine Teilfolge A1 aus A mit den Elementen, deren Schlüsselwert kleiner als x ist und eine Teilfolge A2 mit Elementen ≥ x.

Conquer: A1' := QuickSort (A1); A2' := QuickSort (A2);

Merge: return concat (A1', A2')}

Nach der Aufteilung ist vor der Aufteilung - zumind. solange bis keine Teilung mehr erfolgen kann, d.h. bis für die Teilliste(n) |Ak|=1 gilt.
In diesem Fall ist die Sortierung trivial, da jede einelementige Menge automatisch sortiert ist.

Die beiden Teilfolgen A1=(a0, ..., aj) und A2=(ai, ..., an-1) werden also nach demselben Verfahren rekursiv weiter aufgedröselt bis letztlich einelementige Teilmenge entstehen - anschließend bricht die Rekursion ab.

 

Beispiel

Ein einfaches Beispiel wird die gewonnen Erkenntnisse festigen, und das Verständnis fördern:

Es sei die Zahlenfolge A=(8, 9, 1, 6, 3, 11, 2, 10)= (a0, a1, ..., a7) gegeben. Wir wählen zunächst ein Pivotelement x aus der gegebenen Liste aus. Es ist |A|=8, und 8 div 2 = 4, deshalb setzen wir x:= a4= 6.
Ferner setzen wir i:= 0 und j:=7.

Es ist also A=(8, 9, 1, 6, 3, 11, 2, 10) die Ausgangsliste, wobei die rot markierte Zahl gerade das Pivotelement ist.

Das erste 'Folgenglied' ai links von x, für welches ai≥ x gilt ist a0=8.
Das erste 'Folgenglied' aj rechts von x, für welches aj< x gilt ist a7= 2.
Es gilt j≥i, da 7≥0 und damit müssen wir diese beiden Elemente vertauschen. Die Ergebnisliste ist dann also die Folgende:

A=(2, 9, 1, 6, 3, 11, 8, 10)

Anschließend passen wir noch i:=0+1 und j:=7-1=6, die Indizes, an.

Nun also müssen wir von links ab der Position 1 und von rechts her ab der Position 6 entsprechende Listenelemente finden, welche < oder ≥ x sind. Von links her ist a1= 9 das erste Element ak≥ x (mit k aus {1, 2, ..., 7}).
Von rechts her ist a4= 3 das erste Element ak< x (mit k aus {0, 1, ..., 6}).

Wieder gilt j≥i, da 4≥1, und damit müssen wir diese beiden Elemente vertauschen. Die Ergebnisliste ist dann also die Folgende:

A=(2, 3, 1, 6, 9, 11, 8, 10).

Versucht man nun erneut sein Glück Elemente links und rechts von x zu finden, welche ≥ bzw. < sind als x, so wird man feststellen, dass dies erst für i=j=3 möglich ist. Damit endet der Algorithmus zur Auteilung in zwei Teilfolgen A1 bzw. A2.

Wie bereits weiter oben beschrieben, wendet man nun exakt dieselbe Strategie auf die Teilfolgen A1 bzw. A2 an; dies gerade solange bis einelementige Teillisten entstehen.

Im Anschluss daran führt man die einzelnen, einelementigen (und damit soritierten) Teillisten zu einer gemeinsamen (sortierten) Ergebnisliste zusammen (merge).

Kehren wir nun zu unserem Beispiel zurück. Wir haben also die Ausgangsfolge A=(8, 9, 1, 6, 3, 11, 2, 10) in zwei Teillisten A1 bzw. A2 zerlegt; alle Elemente aus A1 sind kleiner als das zuerst gewählte Pivotelement 6, entsprechend sind alle Elemente aus A2 größer oder gleich als 6 sind. In dieser Rekursionsstufe müssen wir uns also um insgesamt zwei Teilfolgen kümmern. Dazu bestimmen wir wieder die Pivotelemente in der Mitte der Folgen. Es ergeben sich dadurch die Listen A1=(8,9, 1) bzw. A2=( 3, 11, 2, 10). Das zuerst gewählte Pivotelement muss nicht weiter berücksichtigt werden, da dieses bereits an der richtigen Stelle innerhalb des Arrays steht.
Nun ordnen wir wieder die Elemente innerhalb der Teillisten A1 und A2 nach den jeweiligen Pivotelementen um: A1=(1,8,9) bzw. A2=( 3, 2, 10, 11). Die sich aus A1 ergebenden Teillisten wären einelementig, damit muss A1 selbst bereits sortiert sein. An dieser Stelle würde also ein Zweig des rekursiven Baumes abbrechen und die Ergebnisse an die jeweils höhere Stufe zurückgeben. Eine der sich aus A2 ergebenden Teillisten wären leer, für die Zweite müsste man wieder ein Pivotelement bestimmen, usw.!

Das Entwurfsparadigma für Algorithmen "Divide and Conquer" beruht auf einem "Top-Down-Ansatz", d.h. die Problemreduktion bzw. die Problemaufspaltung erfolgt von oben nach unten bzw. vom Problem zu Teilproblemen. Unter Umständen ist es aber auch möglich und sinnvoll gerade umgekehrt, d.h. "Buttom-Up" vorzugehen. Dies ist z.B. bei der Berechnung des Binomialkoeffizienten der Fall - hier ist es überaus sinnvoll die sehr verwandte Strategie der dynamischen Programmierung anzuwenden. Diese fügt die einzelnen Lösungen der Teilprobleme zur Gesamtlösung zusammen - doch mehr dazu an anderer Stelle.

Literatur:

Alle Logos und Warenzeichen auf dieser Seite sind Eigentum der jeweiligen Besitzer und Lizenzhalter.
Im übrigen gilt Haftungsausschluss. Weitere Details finden Sie im Impressum.
Die Inhalte dieser Seite sind als RSS/RDF-Quelle verfügbar.
Die Artikel sind geistiges Eigentum des/der jeweiligen Autoren,
alles andere © 2004 - 2017 by mathematik-netz.de

Seitenerstellung in 0.076 Sekunden, mit 54 Datenbank-Abfragen