Teile und Herrsche 1 SS10

Aus ProgrammingWiki

Archivierte Version vom 2010-04-07T10:42:02+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Was ist überhaupt Divide and Conquer?
2 Das schnelle Sortieren
3 Sortieren durch mischen
4 Vergleich Quicksort und Mergesort
5 Übungen
6 Links und Quellen

Autoren:

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

Was ist überhaupt Divide and Conquer?

In vielen Programmiersprachen wird die Gliederung von Computerprogrammen in Prozeduren, Funktionen, Module, Objekte, Komponenten, Prozesse und Threads nach dem Prinzip teile und herrsche umgesetzt.

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

zerteilen des Problems in Teilprobleme (divide)
lösen der einzelnen Teilprobleme, mittels rekursiver Programmierung (conquer)
Teillösungen zusammenführen zu der Gesamtlösung (konkatenieren)

Ziel

Ziel dieser Methode ist es eine Effiziensverbesserung zu erreichen. Der Lösungsaufwand soll minimiert werden durch die Zerlegung des Hauptproblems in Teilprobleme. Sind die Teilprobleme noch zu aufwändig in der Lösung, werden diese weiter in noch kleinere Teilprobleme zerlegt, bis alle mit einem geringem Aufwand lösbar sind.

Vorteile von DaC

Ein großer Vorteil von Divide und Conquer ist die Zerlegung der Probleme. Dadurch wird es möglich die Probleme in mehreren Instanzen, also sie parallel zu lösen. Beispielweise können, je nach Aufwand des Problems, dafür Multicore Prozessoren oder gar mehrere rechner verwendet werden.

Effizienz von DaC

In der untenstehenden Formel wird erklärt, wie sich der Gesamtaufwand eines Algorithmus aus den Teilproblemen multipliziert mit der Größe der Teilprobleme plus den Aufwand ergibt.

\begin{array}{ccl} T_B & = & 3T_A\left(\left\lceil \frac{n}{2}\right\rceil\right)+d\cdot n\\\\ & \leq & 3 \cdot c \cdot \left( \frac{n+1}{2}\right)^2+d\cdot n\\\\ & \leq & 3 \cdot c \cdot \left( \frac{n}{2} + \frac{1}{2} \right)^2+d \cdot n\\\\ & \leq & 3 \cdot c \cdot \left( \frac{n^2}{4}+2\frac{n}{4}+\frac{1}{4} \right)+d \cdot n\\\\ & \leq & \frac{3}{4}cn^2+\frac{3}{2}cn+\frac{3}{4}c+d \cdot n\\\\ & \leq & \frac{3}{4}cn^2+\left(\frac{3}{2}c+d\right)n+\frac{3}{4}c \end{array}

Es tritt eine Effiziensverbesserung von 25% auf, jedoch ist zubeachten das immer ein rekursiver Aufruf enthalten sein muss.

Das schnelle Sortieren

Beispielsweise wird beim Sortieren mit dem Quicksortalg. die sortierte ergebnisliste aus kleinen jeweils für sich sortierten teillisten zusammengesetzt.

Grundprinzip

Quicksort nimmt eine Liste Zahlen und Teilt sie mit Hilfe eines Hilfselements (Pivotelement) auf. Dabei werden 2 Teillisten erzeugt. Diese beiden Teillisten werden wie folgt gefüllt. In die Sogenannte linke Liste kommen alle Zahlen die kleiner als das Pivotelement sind hinein. Jede Zahl die größer oder Gleich dem Vergleichselement sind kommen in die rechte Teilliste. Das Pivotelement, kann auf verschiedene Art und Weise gewonnen werden. Beispielsweise nimmt man sich willkürliche eine Zahl aus der Gesamtliste herraus oder man berechnet das Element in dem alle Elemente der Liste mit einander addiert und durch die gesamte Anzahl der Listenelemente Teilt, also man das Durchschnittselement berechnet. Dies hat je nach wahl des Pivotelements Auswirkungen auf die Effizienz von Quicksort, was aber nur im Worstcase eine Rolle spielt. Die Teilung der Listen wird solange rekursiv durchgeführt, bis nur noch einzel Elemente in den Teillisten übrig sind. Diese einzelnen listen werden dann von links nach rechts wieder zusammengefügt und erählt somit eine sortierte Liste.

Effzienz

Schemeumsetzung

(define tl
  (lambda (ls v)
    (if (null? ls)
        (values '() '())
        (call-with-values
         (lambda () (tl (cdr ls) v))
         (lambda (li re)
           (let ((x (car ls)))
             (if (< x v)
                 (values (cons x li) re)
                 (values li (cons x re)))))))))
(define quicksort
  (lambda (ls)
    (if (or (null? ls)(null? (cdr ls)))
        ls
        (let ((v (car ls)))
          (call-with-values
           (lambda () (tl (cdr ls) v))
           (lambda  (li re)
              (append
               (quicksort li)
               (list v)
               (quicksort re))))))))

<eval>(quicksort '(2 8 9 13 30 21 7 1 3 6 18 14 20 16 10 12 15 19 25 11 4 5 17))</eval>

Javaumsetzung

public class Quicksorter
{
    private int[] a;
    private int n;

    public void sort(int[] a)
    {
        this.a=a;
        n=a.length;
        quicksort(0, n-1);
    }

    private void quicksort (int lo, int hi)
    {
        int i=lo, j=hi;
        int x=a[(lo+hi)/2];

        //  Aufteilung
        while (i<=j)
        {    
            while (a[i]<x) i++; 
            while (a[j]>x) j--;
            if (i<=j)
            {
                exchange(i, j);
                i++; j--;
            }
        }

        // Rekursion
        if (lo<j) quicksort(lo, j);
        if (i<hi) quicksort(i, hi);
    }

    private void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    public int[] getArray(){
    	return this.a;
    }

}

Sortieren durch mischen

mergesort

Grundprinzip

Effzienz

Schemeumsetzung

Javaumsetzung

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Mergesort{
	  public static void main(String a[]){
	    int i;
	    System.out.println("Wieviel Werte?");
	    int temp = Integer.parseInt(read());
	    int array[] = new int[temp];
	    System.out.println("Geben Sie nun die Werte ein");
	    for(i = 0; i < array.length; i++){
	    	array[i] = Integer.parseInt(read());
	    }
	    
	    System.out.println("Werte vor der Sortierung:\n");
	    for(i = 0; i < array.length; i++)
	      System.out.print( array[i]+"  ");
	    System.out.println();
	    mergeSort_srt(array,0, array.length-1);
	    System.out.print("Werte nach der Sortierung:\n");
	    for(i = 0; i <array.length; i++)
	      System.out.print(array[i]+"  ");
	    System.out.println();
	    System.out.println("PAUSE");
	  }

	  public static void mergeSort_srt(int array[],int lo, int n){
	    int low = lo;
	    int high = n;
	    if (low >= high) {
	      return;
	    }

	    int middle = (low + high) / 2;
	    mergeSort_srt(array, low, middle);
	        mergeSort_srt(array, middle + 1, high);
	    int end_low = middle;
	    int start_high = middle + 1;
	    while ((lo <= end_low) && (start_high <= high)) {
	      if (array[low] < array[start_high]) {
	        low++;
	            } else {
	        int Temp = array[start_high];
	        for (int k = start_high- 1; k >= low; k--) {
	          array[k+1] = array[k];
	        }
	                array[low] = Temp;
	                low++;
	                end_low++;
	                start_high++;
	            }
	        }
	    } 
	  public static String read(){
			String temp = "";
			BufferedReader eingabe = new BufferedReader( new InputStreamReader(System.in));
			try{
				temp = eingabe.readLine();
			}
			catch(IOException e){
				System.out.println("Fehler");
			}
			return temp;
		}
	}

Vergleich Quicksort und Mergesort

Übungen

Aufgabe
Aufgabe
Aufgabe
Aufgabe
Aufgabe

Teile und Herrsche 1 SS10

Inhaltsverzeichnis

Was ist überhaupt Divide and Conquer?

Ziel

Vorteile von DaC

Effizienz von DaC

Das schnelle Sortieren

Grundprinzip

Effzienz

Schemeumsetzung

Javaumsetzung

Sortieren durch mischen

Grundprinzip

Effzienz

Schemeumsetzung

Javaumsetzung

Vergleich Quicksort und Mergesort

Übungen

Links und Quellen

Suche