Teile und Herrsche 1 SS09

Aus ProgrammingWiki

< AuK
Wechseln zu: Navigation, Suche

Loading
Autoren:


Inhaltsverzeichnis

Die Idee

"Teile und Herrsche" (engl. "divide and conquer" bzw. lat. "divide et impera") beschreibt ein Verfahren zur Lösung von Problemen, wobei das Problem

  1. in Teilprobleme zerlegt wird
  2. die Teilprobleme gelöst werden
  3. die Teilprobleme zu einer Lösung vereint werden.


Die folgende Rechnung dient als Beweis, dass eine Effizienzverbesserung auftritt:
Wir nehmen an, dass ein bestimmter Algorithmus ein Problem mit , also , löst. Für ein Algorithmus , der drei dieser Probleme der Größe mit bearbeitet und mit zusammenfügt gilt:



Es tritt also eine Effizienzverbesserung um 25% auf. Da der Aufwand allerdings quadratisch ist, kann man bei großen n den Faktor vernachlässigen. Es ist also offensichtlich das eine Effizienzverbesserung nur auftritt, wenn der Exponent kleiner wird.

Um dies zu erreichen nehmen wir an, das wir einen Algorithmus haben, der die Teilprobleme rekursiv löst. Das bedeutet, dass der Algorithmus auch die Teilprobleme löst, einzig die Basisfälle werden von dem Algorithmus übernommen. Das bedeutet:



Die Anwendung der Meistermethode ergibt:

.

Anhand der Ergebnisses kann man sehen, dass "Teile und Herrsche" aus Effizienzgründen immer mit Rekursion arbeitet.

Quicksort

Das Verfahren

Quicksort wurde 1962 von C.A.R. Hoare entwickelt und ist ein Algotithmus, der nach dem "Teile und Herrsche" - Verfahren arbeitet.
Die Idee von Quicksort besteht darin, jedes Listenelement mit einem Vergleichselement (Pivotelement) zu vergleichen und, je nachdem ob es kleiner oder größer ist, in eine linke oder eine rechte Liste einzufügen. Auf die beiden Teillisten wird jetzt wieder Quicksort angewandt (rekursive Verarbeitung aus Effizienzgründen) und anschließend werden die beiden Listen und das Pivotelement nach folgender Vorschrift zusammengefügt:

  1. linke Liste
  2. Pivotelement
  3. rechte Liste.

Damit die rekursive Abarbeitung terminiert, müssen noch zwei Basisfälle vorgesehen werden:

  1. die Gesamtliste ist leer
  2. die Gesamtliste besteht aus nur einem Element.

In beiden Fällen ist die Liste schon sortiert.

Funktionsorientierte Beschreibung

Die linke bzw. rechte Teilliste wird in dem folgendem Beispiel von den Hilfsfunktionen linke_liste und rechte_liste erzeugt. Das Pivotelement wird durch die Funktion trennelement ermittelt. Die Teillisten werden in der Hauptfunktion durch rekursive Aufrufe von Quicksort ebenfalls sortiert und danach zu einer Erbnisliste zusammengefügt.


Da die beiden Funktion linke_liste und rechte_liste sich nur durch das Relationszeichen unterscheiden, könnte man die Teillistenbildung auch in einer Prozedur abhandeln. Nun besteht hier das Problem, dass in der funktionsorientierten Programmierung Prozeduren nur ein Funktionswert (Rückgabewert) besitzen. Es ist allerdings möglich, die beiden Teillisten wieder in einer Liste zu verpacken. Da die Teillisten aber bei den rekursiven Aufruf wieder benötigt werden, müsste die entsprechende Teilliste vor Aufruf von Quicksort wieder ausgepackt werden. Man sieht, dass dies ein ständiges verpacken und entpacken bedeutet.

Die Lösung liegt im Multiple-value-context. Dabei können Funktionen mehrere Funktionswerte besitzen, die an andere Funktionen weitergegeben und weiterverarbeitet werden können.
Dafür sind zwei Sprachelemente von nöten:

  • (values a1 a2 ... an) liefert n Rückgabewerte
  • (call-with-values p c) nimmt zwei Argumente, einen Producer (p) und einen Consumer (c)

Der Producer ist eine nullstellige Prozedur, der n Rückgabewerte dem n-wertigen Consumer liefert.

Nachfolgend ist eine Prozedur zu sehen, die die Teillisten erzeugt und die jeweiligen Listen getrennt zurück gibt.

Um jetzt Quicksort rekursiv auszuführen, wird in der folgenden Prozedur teillisten mittels call-with-values auf den Consumer angewandt. Der Consumer ruft dann Quicksort einmal für die linke und einmal für die rechte Liste auf.

Effizienz von Quicksort

Best Case

Der Aufwand von Quicksort beträgt im günstigsten Fall (d.h. alle Elemente sind so "gestreut", dass bei der Teillistenbildung immer etwa gleich große Teillisten entstehen):


.

Durch Anwendung der Meistermethode kommt man auf einen Aufwand von:

.

Die Verwendung der Meistermethode liegt nahe, da die allgemeine Form der Gleichung folgender maßen aussieht:


Bei Teile-und-Herrsche haben einige Variablen der allgemeinen Form eine besondere Bedeutung. So steht die Variable für die Anzahl der Teilprobleme und die Variable für die Größe eines Teilproblems.

Worst Case

Ein großer Schwachpunkt von Quicksort liegt im Sortieren einer schon vorher sortierter Liste. Obwohl die Lösung schon vorhanden ist, benötigt Quicksort hier am längsten. Der Grund liegt darin, dass die Teillisten nicht in etwa gleich lang sind sondern eine Teilliste immer leer ist und die andere um eins kleiner als die Ausgangsliste. Dadurch ergibt sich der folgende Aufwand:


.

Darauf wird jetzt die Iterationsmethode angewandt:


Anschließend setzt man jede Zeile in die jeweils darüber stehende ein:

Average Case

Für die Analyse des Average-case nimmt man an, dass jede Teillistenlänge mit gleicher Wahrscheinlichkeit vorkommt, also mit der Wahrscheinlichkeit . Somit gilt

in


.

Dies wird nun eingesetzt:


Jetzt wird die Summe beseitigt:



Harmonische Zahlen:
Bekannte Schranken:

Zusammenfassung

Interne Suchverfahren

Bei der bisherigen Betrachtung haben wir bisher auf eine Forderung von Quicksort verzichtet. Es darf bei Quicksort nicht zusätzlicher Speicher in Anspruch genommen werden, das heißt, man hat während des Sortiervorgangs nur den Speicher zur Verfügung, der von Anfang an von der Eingabeliste belegt wird.

Die Teillistenbildung muss also offensichtlich in der Ausgangsliste durchgeführt werden. Damit jedes einzelne Element in einer Liste angesprochen werden kann, verwenden wir für die Implementierung keine Liste sondern einen Vektor. Desweiteren gehen wir vereinfachend davon aus, dass für alle Felder gilt: für alle . Es muss beachtet werden, dass die Zählung in Programmiersprachen häufig mit 0 anfängt, d.h. .

Das Vergleichselement ist das erste Element im Vektor (). Desweiteren gibt es einen linken und einen rechten Zeiger. Der linke () zeigt auf das erste Element nach v, also . Der rechte zeigt auf das n-te Element (). Der linke Zeiger wird nun nach rechts geschoben, bis gilt: . Der rechte Zeiger wird nach links geschoben bis gilt. Beide Zeiger rücken immer in Einerschritten weiter. Sobald beide Zeiger angehalten haben wird überprüft ob gilt. Wenn ja werden und miteinander vertauscht. Anschließend wird die "Zeigerwanderung" fortgesetzt. Gilt nicht, wird mit vertauscht und anschließend der Vektor als Ergebnis zurückgegeben. Das Vergleichselement v () steht nun an der richtigen Position.

Beispiel:

Mergesort

Das Verfahren

Mergesort ist ein weiteres klassisches Divide & Conquer - Verfahren. Es wurde erstmalig 1945 von John von Neumann vorgestellt, der die nach ihm benannte Von-Neumann-Rechnerarchitektur entwickelt hat. Bei Mergesort, was übersetzt so viel heißt wie Sortieren durch Mischen, wird wie bei Quicksort die Gesamtliste in 2 Teillisten aufgeteilt. Jedoch mit dem Unterschied, dass immer in der Mitte geteilt wird. Das hat zur Folge, dass 2 gleich große Teillisten entstehen (bis auf eine Abweichung von 1, bei ungerader Anzahl an Elementen). Anschließend wird rekursiv Mergesort auf die entstandenen Tellisten angewendet, bis einer der folgenden Basisfälle eintritt:

  1. die Liste ist leer
  2. die Liste besteht aus nur einem Element.

Danach beginnt der Mischen oder Verschmelzen genannte Prozess. Dabei werden die beiden sortierten Teillisten genommen und miteinander verglichen. Dabei wird das 1. Element der ersten Liste mit dem 1. der zweiten Liste verglichen. Ist es kleiner oder gleich, wird es der neuen Gesamtliste angefügt und aus der entsprechenden Teilliste entfernt. Dies geschieht solange, bis beide Teillisten leer sind und somit die Gesamtliste vollständig sortiert ist.

Funktionsorientierte Beschreibung mit Multiple-value-context

Die folgende Funktion teillisten2 ist teillisten aus Quicksort nachempfunden. Sie teilt die als Parameter übergebene Liste in der Mitte und erhält so 2 Teillisten, die gleich groß sind, bzw. bei einer ungeraden Anzahl an Elementen der Ausgangsliste, die linke Liste um 1 kleiner ist als die Rechte. (aufgrund von floor(), welches nur die Ganzzahl zurückgibt. siehe auch: Gaußklammer)

In der nächsten Funktion, die 2 aufsteigend sortierte Listen als Parameter erwartet, werden diese zu einer Liste, der Gesamtliste, hinzugefügt.

Mergesort hat eine ähnliche Implementation wie Quicksort. Auch hier wird wieder der Multiple-Value-Kontext verwendet, um ein abstrakteres Arbeiten zu ermöglichen und sich nicht um Beschränkungen, wie nur ein Rückgabewert je Funktion, kümmern zu müssen.

Effizienzanalysen

Im Gegensatz zur Effizienzanalyse von Quicksort, gibt es bei Mergesort keine Unterscheidung zwischen Worst-, Best- und Average-Case, da hierbei nicht mit einem Pivot-Element gearbeitet wird, sondern "stupide" die Listen immer in der Mitte geteilt werden. Der Algorithmus arbeitet immer gleich, egal ob eine Liste bereits sortiert ist oder nicht. Dies lässt sich zu einer Rekursionsgleichung verallgemeinern, die für viele Verfahren mit "balancierter Zerlegung" in zwei Teilprobleme gilt: Der rekursive Teil () kommt daher, dass ein Problem halbiert wird und man dadurch zwei halbe Probleme hat. bedeutet dass man bei der Halbierung und späteren Verschmelzung einen Konstanten und einen Aufwand hat. Da die Divide- und Merge-Schritte in linearer Zeit, also durchzuführen sind. Mit Hilfe der Meistermethode kann man nun den Aufwand bestimmen. Es liegt hier der zweite Fall vor, somit ergibt sich eine Effizienz des Mergesort-Algorithmus von für den Worst-, Best- und Average-Case.

Besonderheiten

Im Gegensatz zu Quicksort ist Mergesort ein stabiles Sortierverfahren, was bedeutet, dass die Abfolge der Werte bzw. Datensätze die den gleichen Sortierschlüssel besitzen erhalten bleibt. Näheres hierzu ist zum Beispiel auf Wikipedia unter dem Stichwort Stabiles Sortierverfahren zu finden.

Trotz der theoretischen Vorteile von Mergesort gegenüber Quicksort bezüglich Effizienz und Stabilität wird in der Praxis Quicksort bevorzugt, da es im Average-Case in den Konstanten besser ist als Mergesort. Durch diverse Variationen, wie zum Beispiel der zufälligen Auswahl des Pivot-Elementes, lässt sich der Quicksort-Algorithmus so optimieren, dass das Eintreffen des Worst-Cases und damit quadratischer Aufwand sehr unwahrscheinlich ist.

Übungsaufgaben

  1. Implementieren Sie Quicksort anhand des Datenflussdiagramm für das traditionelle Quicksort. Das Datenflussdiagramm finden Sie in den Vorlesungsfolien und im Buch auf Seite 60.
  2. Sortieren Sie wie in der Vorlesung gezeigt, folgende Zahlen mit Hilfe von Quicksort auf Papier. (5 2 3 7 1 3 2 6)
  3. Spielen Sie das interne Suchverfahren für Quicksort einmal auf Papier durch, so dass das 1. Element an der richtigen Stelle in der Liste steht.
  4. Sortieren Sie wie in der Vorlesung gezeigt, folgende Zahlen mit Hilfe von Mergesort auf Papier. (5 2 3 7 1 3 2 6)
  5. Machen Sie sich anhand der folgenden Links mit der Effizienz von verschiedenen Sortieralgorithmen (im besonderen Quick- und Mergesort) vetraut und diskutieren Sie die Beobachtungen in der Gruppe.
Zusatzaufgaben
  1. Analysieren Sie die Berechnung des Average Case für Quicksort. Nutzen Sie dazu das Buch auf Seite 64.
  2. Das Schnellste bisher bekannte Sortierverfahren ist Introsort, machen Sie sich auf der folgenden Internetseite damit vertraut.
Teile_und_Herrsche_1_Übungsaufgaben.pdf (2.9 MB)
Teile_und_Herrsche_1.pdf (7.8 MB)


Eine inhaltliche Fortsetzung zu diesem Thema finden Sie auf den Seiten von Teile und Herrsche 2

Von „https://programmingwiki.de/AuK/Teile_und_Herrsche_1_SS09“
Persönliche Werkzeuge