AuK/Teile und Herrsche 1 SS10

Wiki-Quelltext dieser Seite.

<language>Java</language>
Autoren:
* Raffael Thomas Lang ([mailto:siralang@stud.hs-zigr.de siralang@stud.hs-zigr.de])
* Sebastian Kramer ([mailto:sisekram@stud.hs-zigr.de 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 eine Effiziensverbesserung zu erreichen. Der Lösungsaufwand soll minimiert werden durch die Zerlegung des Hauptproblems.

===Vorteile von DaC===

Teilprobleme können parallelisiert werden, d.h. auf mehreren Rechnern ist die gleichzeitige Berechnung möglich.

===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.

::<math>
\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}
</math><br /><br />

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===

===Effzienz===

===Schemeumsetzung===

===Javaumsetzung===

<code id="4bbbd351d3e55">
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;
    }

}
</code>


==Sortieren durch mischen==

mergesort

===Grundprinzip===

===Effzienz===

===Schemeumsetzung===

===Javaumsetzung===
<code id="4bbbd1dc97bd3">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;
		}
	}</code>

==Vergleich Quicksort und Mergesort==

==Übungen==
# Aufgabe
# Aufgabe
# Aufgabe
# Aufgabe
# Aufgabe
==Links und Quellen==