Divide & Conquer

Divide & Conquer ist eine Abkürzung für Divide & Conquer.

Divide&Conquer ("teile und herrsche") ist ein Verfahren, das vielfach für Algorithmen verwendet wird. Besonders aber zum Sortieren.

Bücher zum Thema bei Amazon.de

Es basiert darauf, dass man ein Problem, welches hier sehr gro ist, in viele kleine Probleme zerlegt und so nur noch die einzelnen Teilprobleme zu lösen braucht.

Hat man zum Beispiel eine sehr lange Zahlenfolge, so ist es sehr zeitaufwändig und so ist es nicht gerade benutzerfreundlich, die Folge auf einfache Weise zu sortieren (die Rede ist z.B. von Folgen mit Objekten x>10000).

So hat man sich im Laufe der Zeit ein neues System einfallen lassen, um solche Zahlenfolgen zu sortieren

und zwar mithilfe des Divide & Conquer-Prinzips.

Dass es dabei wiederum verschiedene Arten von Divide & Conquer-basierten Sortieralgorithmen gibt, erklärt sich von selbst.

Als kleines Beispiel für das Divide & Conquer-Prinzips

möchte ich hier mit dem Mergesortalgorithmus (gesprochen: Mörtschsort) ansetzen.

Ich werde ihn dazu kurz an einer Beispielfolge beschreiben:

Als Folge haben wir 9,3,2,5,8,15,21,1

Diese soll sortiert werden!

Also wenden wir das Divide & Conquer System an und teilen die Folge auf (in der Mitte)

Wir erhalten:

              9,3,2,5 und 8,15,21,1

also zwei Folgen die schon kleiner sind.

Jetzt geht es weiter bis jede Zahl für sich als eine Folge dasteht!

also:      9,3 und 2,5 und 8,15 und 21, 1

      9 und 3 und 2 und 5 und 8 und 15 und 21 und 1

jetzt hat jede Zahl ein Element!

Als nächstes setzt man die Folgen genau andersherum wieder zusammen. Dabei vergleicht man die Elemente miteinander: Ist das erste gröer, so steht es an erster Stelle, wenn nicht, an zweiter.

Beispielhaft sieht das hier folgendermaen aus:

      9 und 3 und 2 und 5 und 8 und 15 und 21 und 1

wird in 2er Gruppen zusammengesetzt und sieht dann so aus:

          3,9 und 2,5 und 8,15 und 1,21

Jetzt werden die Elemente wieder zu 4er Gruppen zusammengesetzt (wieder vergleichen und beim Einsetzen sortieren!)

          2,3,5,9 und 1,8,15,21

Und dann wieder zu einem Element, und die Folge ist sortiert.

            1,2,3,5,8,9,15,21

Auf diese Weise hat Mergesort und auch alle anderen Sortieralgorythmen nach dem Divide & Conquer Verfahren eine sehr geringe Laufzeit (logarithmisch)

und kann so auch für groe Zahlen benutzt werden.

Der schnellste bekannte Sortieralgorithmus ist Quicksort, der auch nach dem Divide & Conquer-Prinzip funktioniert (jedoch auf andere Weise). Diesen möchte ich hier jedoch nicht anführen, da dies sonst zu umfangreich würde. Ich bitte um Verständnis.

Trotzdem habe ich den Quellcode von Quicksort für Java einmal umgesetzt und möchte ihn nicht vorenthalten:

public class Quick

{

    private int[] a;

    public void sort(int[] a0)

    {

        a=a0;

        quicksort(0, a.length-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]
            while (a[j]>x) j--;

            if (i<=j)

            {

                tausch(i, j);

                i++; j--;

            }

        }

        // Rekursion

        if (lo
        if (i
    }

    private void tausch(int i, int j)

    {

        int t=a[i];

        a[i]=a[j];

        a[j]=t;

    }

}    // end class QuickSorter

Wichtig ist hier der rekursive Aufruf der Methode quicksort(int lo, int hi)!

Wer nicht wei, was das ist, der kann bald (hoffentlich) unter dem Begriff Rekursiver Aufruf nachlesen was damit gemeint ist.

Zusammenfassung:

Divide & Conquer ist Englisch und heit übersetzt "teile und herrsche".

Man benutzt dieses System häufig bei Sortierverfahren.

Sortierverfahren nach diesem System sind z.B. Mergesort, Quicksort und Heapsort.

Sie sind besonders für groe Zahlenfolgen geeigent, da sie eine sehr geringe Laufzeit haben und auch nicht viel Speicherplatz benötigen.

(logarithmische Laufzeit)

-Ende-

Diesen Begriff auf Ihrer Homepage einbinden | Nach diesem Begriff weitersuchen