Sortieren[Bearbeiten]

Dieses Kapitel gibt eine grundlegende Einführung in das Thema Sortieren. Sortieren ist ein grundlegendes Problem in der Informatik. Es beinhaltet das Ordnen von Dateien mit Datensätzen, die Schlüssel enthalten und das Umordnen der Datensätze, so, dass eine klar definierte Ordnung der Schlüssel (numerisch/alphabetisch) besteht. Eine Vereinfachung ist die Betrachtung der Schlüssel, z.B. ein Feld von int-Werten.

Ordnung[Bearbeiten]

Partielle Ordnung

Sei M eine Menge und

\leq \subseteq (MxM)=

binäre Relation.

Es gilt:

Reflexivität $x\leq x\ \forall x\in M$
Transitivität $x\leq y\land y\leq z\to x\leq z~\forall x,y,z\in M$
Antisymmetrie $x\leq y\land y\leq x\to x=y~\forall x,y\in M$

Strikter Anteil einer Ordnungsrelation $\leq$

x<y:=x\leq y\land x\neq y

Totale Ordnung

Partielle Ordnung $(M,\leq )$
Trichotomie ("Dreiteilung") $x<y\lor x=y\lor x>y~\forall x,y\in M$

Grundbegriffe[Bearbeiten]

Das Verfahren ist intern, wenn auf Hauptspeicherstruktur, wie Felder und Listen sortiert wird. Hingegen ist es extern, wenn die Datensätze auf externen Medien, wie Festplatten und weitere sortiert werden. Die Annahmen sind eine totale Ordnung, aufsteigend vs. absteigend und der Platzbedarf.

Problembeschreibung[Bearbeiten]

Als Eingabe haben wir eine Folge von Zahlen $\langle a_{1},...,a_{n}\rangle$ . Als Ausgabe haben wir die Permutation $\langle a'_{1},...,a'_{n}\rangle$ der Zahlen mit der Eigenschaft $a'_{1}\leq a'_{2}\leq ,...,a'_{n}$ . Die Sortierung erfolgt nach einem Schlüssel, z.B. Zahlen. In Programmen ist es übertragbar auf beliebige Datenstrukturen mit Schlüssel.

Stabilität[Bearbeiten]

Ein Sortierverfahren heißt stabil, wenn es die relative Reihenfolge gleicher Schlüssel in der Datei beibehält. Beispiel: alphabetisch geordnete Liste von Personen soll nach Alter sortiert werden. Personen mit gleichem Alter sollen weiterhin alphabetisch geordnet bleiben:

Name          Alter               Name          Alter
Aristoteles   24                  Aristoteles   24
Platon        28     SORTIEREN →  Platon        28
Sokrates      30                  Theophrastos  28
Theophrastos  28                  Sokrates      30

Sortieralgorithmen[Bearbeiten]

Java Stub[Bearbeiten]

public class InsertionSort extends Sort {
 /*
  * Sortiert die Sequenz a nach dem Verfahren  
  * „Sortieren durch Einfügen“
  */ 
 @Override
 public void execute(int[] a) {
  // Elemente: a[0], … , a[n-1] 
  int n=a.length;
  int x; 
  int j;
 
  // HIER KOMMT DER SORTIERALGORITHMUS
  // assert: a[0] <= … <= a[n-1] 
 }
}

Vergleichsbasiertes Sortieren[Bearbeiten]

Das vergleichbasierte Sortieren ist ein wichtiger Spezialfall des Sortierproblems. Zur Sortierung können nur direkte Vergleiche zweier Werte benutzt werden. Der Wertebereich der Schlüssel kann beliebig sein. Als Eingabe haben wir ein Array ganzer Zahlen und als Ausgabe ein sortiertes Array mit den selben Zahlen mit erhaltenen Mehrfachvorkommen. Einige Sortierverfahren sind effizienter, wenn Listen anstatt Arrays benutzt werden.

Sortierinterface in Java[Bearbeiten]

public interface Sort {

   /**
    * sorts the given array.
    * @param toSort - array to sort.
    */
    public void execute(int[] toSort);
}

Ausblick[Bearbeiten]

Auf den folgenden Seiten werden die Sortieralgorithmen Insertion Sort, Selection Sort, Merge Sort und Quick Sort behandelt.

Literatur[Bearbeiten]

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5.2 zu finden.

InsertionSort[Bearbeiten]

Dieses Kapitel behandelt die Sortiermethode InsertionSort oder auch Sortieren durch Einfügen genannt. Die Idee des Algorithmus ist, die typische menschliche Vorgehensweise, etwa beim Sortieren eines Stapels von Karten umzusetzen. Das heißt es wird mit der ersten Karte ein neuer Stapel gestartet. Anschließend nimmt man jeweils die nächste Karte des Originalstapels und fügt diese an der richtigen Stelle im neuen Stapel ein.

Beispiel[Bearbeiten]

Java Code[Bearbeiten]

void  InsertionSort(int[] F) {  

int m,j;
for (int i = 1; i < F.length; i++){
      j = i;
      m = F[i];
      while (j > 0 && F[j-1] > m) {
             /*verschiebe F[j-1] nach rechts */
              F[j] = F[j-1];
              j--;
       }
       F[j] = m;
     }
}

Das Array hat F.length viele Elemente von Position 0 bis F.Length-1. Wenn F[j-1] größer m ist, dann wird F[j-1] nach rechts verschoben. Am Ende des Algorithmus wird F[i] an Position F[j] gesetzt.

Analyse[Bearbeiten]

Theorem der Terminierung[Bearbeiten]

Das Theorem der Terminierung besagt, dass der Algorithmus InsertionSort für jede Eingabe int[] F nach endlicher Zeit terminiert.

Beweis[Bearbeiten]

Die Laufvariable i in der äußeren for‐Schleife wird in jedem Durchgang um eins erhöht und wird damit irgendwann die Abbruchbedingung (eine Konstante)erreichen. Die Laufvariable j der inneren while‐Schleife wird in jedem Durchgang um eins verringert und somit die Schleifenbedingung j>0 irgendwann nicht mehr erfüllen.

Theorem der Korrektheit[Bearbeiten]

Das Theorem der Korrektheit besagt, dass der Algorithmus InsertionSort das Problem des vergleichsbasierten Sortierens löst. Beweisen

Beweis[Bearbeiten]

Wir zeigen, dass die folgende Aussage eine Invariante der äußeren for‐Schleife ist (d.h. sie ist am Ende eines jeden Schleifendurchgangs gültig): Das Teilarray F[0..i] ist sortiert Damit gilt auch, dass nach Abbruch der for‐Schleife das Array F[0..n]=F (mit n=F.length‐1) sortiert ist. Zu zeigen ist nun, dass am Ende jeden Durchgangs der äußeren for Schleife F[0...i] sortiert ist. Dies wird durch Induktion nach i gezeigt. Für i=1 gilt im ersten Durchgang wird das erste Element F[0] mit dem zweiten Element F[1] verglichen und ggfs. getauscht um Sortierung zu erreichen (while‐Bedingung). Für $i\to i+1$ gilt angenommen F[0...i] ist am Anfang der äußeren for‐Schleife im Durchgang i+1 sortiert. In der while‐Schleife werden Elemente solange einen Platz weiter nach hinten verschoben, bis ein Index k erreicht wird, sodass alle Elemente mit Index 0..k‐1 kleiner/gleich dem ursprünglichen Element an Index i+1 sind (Induktionsbedingung) und alle Elemente mit Index k+1...i+1 größer sind (while‐Bedingung). Das ursprüngliche Element an Index i+1 wird dann an Position k geschrieben. Damit gilt, dass F[0...i+1] sortiert ist.

Theorem der Laufzeit[Bearbeiten]

Das Theorem der Laufzeit besagt, dass die Anzahl der Vergleichsoperationen von Insertion Sort im besten Fall $\Theta (n)$ ist und im durchschnittlichen und schlechtesten $O(n^{2})$ .

Beweis[Bearbeiten]

Für die Aufwandsanalyse sind die Anzahl der Vertauschungen und der Vergleiche relevant. Allerdings dominieren die Vergleiche die Vertauschungen, das heißt es werden wesentlich mehr Vergleiche als Vertauschungen benötigt. Wir müssen in jedem Fall alle Elemente i:=1 bis n-1 durchgehen, d.h. immer Faktor n-1 für die Anzahl der Vergleiche. Dann müssen wir zur korrekten Einfügeposition zurückgehen

Im besten Fall ist die Liste schon sortiert. Die Einfügeposition ist gleich nach einem Schritt an Position i-1, d.h. die Anzahl der Vergleiche ist gleich der Anzahl der Schleifendurchläufe = n-1. Bei jedem Rückweg zur Einfügeposition nimmt man den Faktor 1. Somit beträgt die Gesamtzahl der Vergleiche: $(n-1)\cdot 1=n-1$ . Für große Listen lässt sich $n-1\approx n$ abschätzen. Damit haben wir einen linearen Aufwand.

Im mittleren Fall ist die Liste unsortiert. Die Einfügeposition befindet sich wahrscheinlich auf der Hälfte des Rückwegs. Bei jedem der n-1 Rückwege, muss ein (i-1)/2 Vergleich addiert werden. Die Gesamtzahl der Vergleiche beträgt dann:

$(n-1)/2+(n-2)/2+(n-3)/2+...+2/2+1/2$

$={\frac {(n-1)+(n-2)+(n-3)+...+2+1}{2}}$

$={\frac {1}{2}}\cdot {\frac {n\cdot (n-1)}{2}}$

$={\frac {n\cdot (n-1)}{4}}$

$\approx {\frac {n^{2}}{4}}$

Daraus ergibt sich ein quadratischer Aufwand, wenn konstante Faktoren nicht berücksichtigt werden.

Im schlechtesten Fall ist die Liste absteigend sortiert. Die Einfügeposition befindet sich am Ende des Rückgabewertes bei Position 1. Bei jedem der n-1 Rückwege müssen i-1 Elemente verglichen werden (d.h. alle vorherigen Elemente F[1...i-1]). Analog zu vorhergehenden Überlegungen, gibt es hier aber die doppelte Rückweglänge. Daraus ergibt sich die Gesamtanzahl der Vergleiche:

$(n-1)+(n-2)+(n-3)+...+2+1$ $={\frac {n\cdot (n-1)}{2}}$ $\approx {\frac {n^{2}}{2}}$

Daraus ergibt sich ein quadratischer Aufwand, wenn konstante Faktoren nicht berücksichtigt werden.

Optimierung[Bearbeiten]

In der vorgestellten Version des Algorithmus wird die Einfügeposition eines Elements durch (umgekehrte) sequenzielle Suche gefunden. Verwendet man hier binäre Suche (das Teilarray vor dem aktuellen Element ist sortiert!) kann die Anzahl der Vergleichsoperationen gesenkt werden zu O(n log n) (genauere Analyse zeigt, dass die Zahl noch kleiner ist)

Literatur[Bearbeiten]

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5.2.2 zu finden.

SelectionSort[Bearbeiten]

Dieses Kapitel behandelt die Suchmethode SelectionSort. Die Idee dieses Suchalgorithmus ist, den jeweils größten Wert im Array zu suchen und diesen an die letzte Stelle zu tauschen. Anschließend fährt man mit der um 1 kleineren Liste fort.

Beispiel[Bearbeiten]

Java Code[Bearbeiten]

void  SelectionSort(int[] F) {  
   int  meinSackJuckt = F.length -1;
   while (meinSackJuckt >= 0) {
     /*bestimme größtes Element links v. Marker*/
       int max = 0;  /* Indexposition*/
       for (int i = 1; i <= meinSackJuckt; i++){
           if (F[i] > F[max])
               max = i;
       swap(F, meinSackJuckt, max);
       meinSackJuckt--;   /*verkleinere Array */
   }
void  swap(int[] F, int idx1, int idx2) {  
    int tmp = F[idx1];
    F[idx1] = F[idx2];
    F[idx2] = tmp;
}

In Java benutzt man die Hilfsmethode swap, welche zwei Elemente im Array vertauscht.

Analyse[Bearbeiten]

Theorem der Terminierung[Bearbeiten]

Das Theorem der Terminierung besagt, dass der Algorithmus SelectionSort für jede Eingabe int[]F nach endlicher Zeit terminiert.

Beweis[Bearbeiten]

Die Variable marker wird zu Anfang des Algorithmus auf einen positiven endlichen Wert gesetzt und in jedem Durchgang der äußeren while‐Schleife um 1 verkleinert. Abbruch der while Schleife erfolgt, wenn marker kleiner 0 ist, also wird die while‐Schleife endlich oft durchlaufen. Die innere for‐Schleife hat in jedem Durchgang marker‐viele (also endlich viele) Durchläufe.

Theorem der Laufzeit[Bearbeiten]

Das Theorem der Laufzeit besagt, dass der Algorithmus SelectionSort eine Laufzeit von $\Theta (n^{2})$ hat im besten, mittleren und schlechtesten Fall.

Beweis[Bearbeiten]

Die äußere while‐Schleife wird genau n‐mal (n=F.length) durchlaufen. Dort werden somit n Vertauschungen vorgenommen (=jeweils konstanter Aufwand). Die innere for‐Schleife hat im i‐ten Durchlauf der while‐Schleife n‐i Durchläufe mit jeweils einem Vergleich, deswegen insgesamt

$(n-1)+(n-2)+(n-3)+...+1$ $={\frac {n\cdot (n-1)}{2}}\approx {\frac {n^{2}}{2}}$

Die Anzahl der Vergleiche ist im besten, mittleren und schlechteste Fall identisch, da immer das komplette Array durchlaufen wird.

Literatur[Bearbeiten]

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5.2.3 zu finden.

BubbleSort[Bearbeiten]

Dieses Kapitel behandelt die Suchmethode BubbleSort. Es handelt sich hierbei um ein sehr bekanntes, aber nicht besonders effizientes Sortierverfahren. Es ist eine einfach zu implementierende zugrunde liegende Vorstellung. Bei einer vertikalen Anordnung von Elementen in Form von Luftblasen (bubbles) werden wie in einer Flüssigkeit von alleine sortiert, da die größeren Blasen die kleiner „überholen“. Das Grundprinzip ist somit die Folge immer wieder zu durchlaufen und dabei benachbarte Elemente, die nicht die gewünschte Sortierreihenfolge haben, zu vertauschen. Das bedeutet Elemente die größer sind als ihre Nachfolger, überholen diese.

Beispiel[Bearbeiten]

Java Code[Bearbeiten]

void  BubbleSort(int[] F) {  
     
    for (int n= F.length; n >1; n=n-1) { 
      for (int i =0; i < F.length-1; i++)  {
           if (F[i] > F[i+1]){
               swap(F, i, i+1);
           }
       }
    }
}

Hierbei handelt es sich um die einfachste Form, doch der Algorithmus kann auch optimiert werden. Wir haben beobachtet, dass die größte Zahl in jedem Durchlauf automatisch an das Ende der Liste rutscht. Daraus folgt in jedem Durchlauf j reicht die Untersuchung bis Position n-j, das heißt im j.ten Durchlauf sind die Elemente zwischen den Positionen n-j und n-1 sortiert. Wenn keine Vertauschung mehr stattfindet, soll das Programm abbrechen.

void  BubbleSort(int[] F) {  
   boolean swapped;
   int n = F.length;
   do {
       swapped = false;
       for (int i =0; i < n-1; i++)  {
           if (F[i] > F[i+1]){
               swap(F, i, i+1);
               swapped = true;
           }
       }
       n--;
    }while (swapped);
  
}

Aufwand[Bearbeiten]

Im besten Fall beträgt der Aufwand n. Im mittleren Fall ohne Optimierung $n^{2}$ und mit Optimierung ${\frac {n^{2}}{2}}$ . Im schlechtesten Fall ohne Optimierung beträgt der Aufwand $n^{2}$ und mit Optimierung ${\frac {n^{2}}{2}}$ .

Literatur[Bearbeiten]

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5.2.4 zu finden.

MergeSort[Bearbeiten]

In diesem Kapitel wird der Sortieralgorithmus MergeSort behandelt.

Rückblick[Bearbeiten]

Die bisherige Verfahren erforderten einen direkten Zugriff auf einzelne Elemente (z.B. in einem Array). Sie sind besonders geeignet für internes Sortieren. Allerdings gibt es Probleme, wenn Daten sortiert werden sollen, die nicht in den den Hauptspeicher passen. Daher brauchen wir andere Verfahren, die nicht zwingend Elemente intern verwalten. Das Prinzip dieser Algorithmen ist das Sortieren in mehreren Phasen oder Schritten.

Idee[Bearbeiten]

MergeSort ist ein Divide-and-Conquer Algorithmus zum vergleichsbasierten Sortieren. Zuerst wird die zu sortierende Folge in zwei Teile geteilt. Anschließend werden beide Teile voneinander getrennt sortiert. Zuletzt werden beide Teilergebnisse in der richtigen Reihenfolge zusammen gemischt.

Beispiel[Bearbeiten]

Algorithmus[Bearbeiten]

void mergeSort(int[] F) {
    int[] tmpF = new int[F.length];
    mergeSort(F, tmpF, 0, F.length -1);
}


void mergeSort(int[] F, int[] tmpF, int left,int right)
{ 
    if (left < right) {
        int m = (left + right)/2;
        mergeSort(F, tmpF, left, m);
        mergeSort(F, tmpF, m+1, right);
        merge(F, tmpF, left, m+1, right);
    }
}
void merge(int[] F, int[] tmpF, int startLeft, int startRight, int endRight) {
  int endLeft = startRight-1;
  int tmpPos = startLeft;
  int numElements = endRight – startLeft +1;
  while (startLeft <= endLeft && startRight <= endRight)
     if (F[startLeft] < F[startRight])
         tmpF[tmpPos++] = F[startLeft++];
     else
         tmpF[tmpPos++] = F[startRight++];
  
  while (startLeft <= endLeft)
      tmpF[tmpPos++] = F[startLeft++];
  while (startRight <= endRight)
      tmpF[tmpPos++] = F[startRight++];
  
  for (int i = 0; i < numElements; i++, endRight--)
         F[endRight] = tmpF[endRight];
}

Das Abbruchkriterium für den rekursiven Aufruf ist eine einelementige Liste.Der Misch-Vorgang erfordert in der Regel doppelten Speicherplatz, da eine neue Folge aus den beiden Sortierten generiert werden muss. Eine Alternative ist das Mischen in einem Feld (in-place), das erfordert aber aufwendiges Verschieben.

Analyse[Bearbeiten]

Theorem der Terminierung[Bearbeiten]

Das Theorem der Terminierung besagt, dass der Algorithmus MergeSort für jeden Eingabe int[]F nach endlicher Zeit terminiert.

Beweis[Bearbeiten]

Zeige zunächst, dass jeder Aufruf mergeSort(int[] F, int[] tmpF, int left,int right) terminiert:  

Falls lef < right nicht gilt, terminiert der Aufruf sofort
Andernfalls rufen wir mergeSort rekursiv auf, wobei entweder lef einen echt größeren oder right einen echt kleineren Wert erhält. In jedem Fall wird nach einem gewissen rekursiven

Abstieg irgendwann lef<right nicht mehr gelten.

Theorem der Korrektheit[Bearbeiten]

Das Theorem der Korrektheit besagt, dass der Algorithmus MergeSort das Problem des vergleichsbasierten Sortierens löst.

Beweis[Bearbeiten]

Durch Induktion nach n = F.length. Annahme n=2 für eine ganze Zahl k.

n=1: Für n=1 ist der erste Aufruf der mergeSort Hilfsmethode mergeSort(F, tmpF, 0, 0)

und somit gilt nicht lef < right. Die Methode terminiert ohne Änderung an F. Dies ist korrekt, da jedes einelementige Array sortiert ist.

n/2 → n: Sei F[0...n‐1] ein beliebiges Array. Der erste Aufruf mergeSort(F, tmpF, 0, n-1) erfüllt lef<right und es werden folgende Rekursive Aufrufe getätigt: mergeSort(F, tmpF, 0, n/2-1) mergeSort(F, tmpF, n/2, n-1) Beide Aufrufe erhalten ein Array der Länge n/2. Nach Induktionsannahme gilt, dass anschliessend sowohl F[0...n/2‐1] als auch F[n/2...n‐1] separat sortiert sind. Noch zu zeigen ist, dass merge korrekt zwei sortierte Arrays in ein sortiertes Array mischt.

Theorem der Laufzeit[Bearbeiten]

Das Theorem der Laufzeit besagt, dass der Algorithmus MergeSort eine Laufzeit von $\Theta (nlog_{2}n)$ hat. Diese Laufzeit ist die selbe für den besten, mittleren und schlechtesten Fall.

Beweis[Bearbeiten]

$T(n):=\left\{{\begin{array}{ll}\Theta (1)&{\text{für }}n\leq 1\\2T(n/2)+\Theta (n)&sonst\end{array}}\right.$

Nun wenden wir das Master Theorem an.

Im 2. Fall, wenn $f(n)\in \Theta (n^{log_{b}a}*ld^{k}n){\text{ für ein }}k\geq 0{\text{ dann }}T(n)=\Theta (n^{log_{b}a}*ld^{k+1}n)$

Hier ist a=2 und b=2 und es folgt $n^{log_{b}a}=n^{log_{2}2}=n^{1}=n.$

Es ist zudem f(n)=n und es gilt für k=0:

$n\in \Theta (n~ld^{k}~n)=\Theta (n)$

Es folgt $T(n)\in \Theta (n~ld^{k+1}~n)=\Theta (n~ld~n).$

Literatur[Bearbeiten]

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5.2.5 zu finden.

Zwischenbemerkungen[Bearbeiten]

An dieser Stelle gibt es einige Zwischenbemerkungen zu den vorgestellten Sortieralgorithmen.

Einordnung der elementaren Sortierverfahren[Bearbeiten]

	Implementierung Array	Implementierung Liste
greedy	selection sort, bubble sort	insertion sort
divide-and-conquer	quicksort	merge sort

Eigenschaften[Bearbeiten]

Divide and conquer bedeutet teile und herrsche. Dabei wird das eigentliche Problem so lange in kleiner und einfachere Teilprobleme zerlegt, bis man diese lösen kann. Oft können Teilprobleme parallel gelöst werden. Des Weiteren sind Teilprobleme „eigenständige“ Probleme. Anschließend werden die Teillösungen zu einer Gesamtlösung zusammengeführt.

Greedy bedeutet gierig. Hierbei wird schrittweise ein Folgezustand ausgewählt, der aktuell den größten Gewinn und das beste Ergebnis verspricht. Die Auswahl des Folgezustands erfolgt anhand von Bewertungsfunktionen und Gewichtsfunktionen. Ein Problem dabei ist, dass oft nur ein lokales Maximum gewählt wird. Mehr dazu im Thema Entwurfsmuster.

Generische Implementierung[Bearbeiten]

Algorithmen werden „parametrisiert“ durch Vergleichsoperator. Im Paket java.lang gibt es dafür ein Interface Comparable. Der Aufruf der Vergleichsmethode a.compareTo(b) liefert ein Zahl <0, =0, >0 für a<b, a=b und a größer b. Das Muster für Objekte vom Referenztyp Comparable lautet:

public class MyObject  implements Comparable {
      MyType data;
      public int compareTo (MyObject obj) {
            if („this.data < obj.data“) return -1;
            if („this.data = obj.data“) return 0;
            if („this.data > obj.data“) return 1;
     }
}

Das Muster für Aufrufe in Klassenmethoden bei Suchverfahren lautet:

 

public static int binarySearch( Comparable[] f,
       Comparable a,  int l,  int r) {
           int p = (l+r)/2; 
           int c = f[p].compareTo(a);
  ... }

Listenimplementierung generisch[Bearbeiten]

 

public class MyObject implements Comparable {. . .}

public class Node { 
    MyObject data;    
    Node next;   
}
public class OrderedList { 
 private Node head;  
 public OrderedList sort ( ) {. . .}

Interne Hilfsmethoden[Bearbeiten]

int findMin(){...}
- F.findMin() bestimmt den Index des minimalen Elements von OrderedList F
void insertLast(int a)
- F.insertLast(a) fügt Element mit Index (Key) a an das Ende von F an
void deleteElem(int a)
- F.deleteElem(a) löscht Element mit Index a aus der Liste F
Aufwand: jeweils = O(n), wenn n = Anzahl der Objekte in Liste

MergeSort generisch[Bearbeiten]

 

public class OrderedList {
   OrderedNode head;
   int length;
   // ...

   /**    * Sorts this list in non-descending order       */
   public void mergeSort() {
     OrderedList aList, bList; // the divided lists
     OrderedNode aChain; // start of first node chain
     OrderedNode bChain; // start of second node chain
     OrderedNode tmp; // working node for split

     // trivial cases
     if ( (head==null) ||  (head.next == null) ) 
          return; 
// divide: split the list in two parts
    aChain = head;
    tmp = head;      // init working node for split
    // advance half of the list
    for (int i=0; i < (length-1) / 2; i++)
      tmp=tmp.next;

    // cut chain into aChain and bChain
    bChain=tmp.next;
    tmp.next=null;

    // encapsulate the two node chains in two lists 
    aList = new OrderedList();
    aList.head=aChain;
    aList.length=length/2;
    bList = new OrderedList();
    bList.head=bChain;
    bList.length=length - aList.length;

    // conquer: recursion
    aList.mergeSort(); bList.mergeSort();
    // join: merge
    merge(aList, bList);
  }
}

Aus Gründen der Übersichtlichkeit erzeugt dieses Programm im Divide-Schritt jeweils gekapselte Zwischenlisten vom Typ OrderedList. In der Praxis würde man hierauf verzichten und rein auf Knoten-Ketten arbeiten, da insgesamt O(n) Objekte vom Typ OrderedList erzeugt und wieder vernichtet werden(maximal O(log n) davon sind gleichzeitig aktiv).

QuickSort[Bearbeiten]

In diesem Kapitel wird der Sortieralgorithmus QuickSort behandelt.

Idee[Bearbeiten]

Es gibt eine rekursive Aufteilung (wie bei MergeSort), aber hier werden Mischvorgänge vermieden (speicherintensiv!). Die Teillisten werden in zwei Hälften geteilt bezüglich eines Pivot-Elements, wobei in einer Liste alle Elemente größer als das PivotElement sind und in der anderen Liste alle kleiner. Das Pivot Element ist ein beliebiges Element der Liste/Folge, z.B. das linke, mittlere oder rechte Element.

Beispiel[Bearbeiten]

Vertauschen von Elementen[Bearbeiten]

Für gegebenes Pivot-Element p wird die Folge von links durchsuchen, bis das Element gefunden wurde, das größer oder gleich p ist. Und gleichzeitig wird die Folge von rechts durchsuchen, bis das Element gefunden ist, das kleiner p ist. Dabei werden die Elemente ggf. getauscht.

Sortierprinzip[Bearbeiten]

Sortieren einer Folge F[u...o] nach dem „divide-and-conquer“Prinzip. Divide heißt die Folge F[u...o] wird in zwei Teilfolgen F[u...p-1] und F[p+1...o] geteilt. Die zwei Teilfolgen haben folgende Eigenschaften:

F[i] ≤ F[p] für alle i = u,...,p-1
F[i] > F[p] für alle i = p+1, …, o

Conquer bedeutet, dass die Teilfolgen sortiert werden. Mit combine werden die Teilfolgen zu F[u...o] verbunden. Vergleiche sind an dieser Stelle nicht erforderlich, da die Teilfolgen bereits sortiert sind.

Pivot Element[Bearbeiten]

Im Prinzip muss man nicht das letzte Element als Pivot‐Element wählen. Je nach Verteilung der Daten, kann es sinnvoll sein ein anderes Element zu wählen. Wenn beispielsweise die Liste schon fast sortiert ist, sollte man immer das mittlere Element wählen Eine optimale Rekursion erhält man, wenn man immer den Median als Pivot-Element wählt (dieser ist aber nicht direkt bestimmbar, dafür müsste man die Liste erst sortiert haben. Hat man ein Pivot-Element ausgewählt, tauscht man dies einfach mit dem letzten Element und benutzt den Algorithmus wie zuvor.

Algorithmus[Bearbeiten]

void quickSort(int[] F, int u, int o) {
     if (u < o) {
        int p = (u+o)/2;
        int pn = zerlege(F,u,o,p);
        quickSort(F,u,pn-1);
        quickSort(F,pn+1,o);
     }
int zerlege(int[] F, int u, int o, int p) {
     int pivot = F[p];
     int i = u;
     int j = o;    
  
     while (i < j) {
         while (F[i] < pivot)
             i++;
         while (F[j] > pivot)
             j--;
         if (i < j) {
             swap(F,i , j );
         }
     }
     return i;
} 
int zerlege(int[] F, int u, int o, int p) {     
     int pivot = F[p];

     //Tausche Pivot-Element mit dem letzten Element 
     //kann entfallen, wenn immer p=o gewählt wird
     swap(F,p, o);    
     int pn = u;

     //bringe kleinere Elemente nach vorne und größere nach hinten
     for (int j = u; j < o; j++) {    
          if (F[j] <= pivot){ 
               swap(F,pn, j );
               pn++;
          }
     }

     //bringe das Pivot-Element an die richtige Position und gebe diese zurück
     swap(F,pn, o);     
     return pn;
} 

void swap(int[] f, int x, int y){   //Hilfsmethode zum Vertaucshen
   int tmp = f[x];
   f[x] = f[y];
   f[y] = tmp;
}

}

P gibt an ,an welcher Position das Pivot Element ist. Bei diesem Beispiel ist es in der Mitte. Es kann aber auch an Stelle o oder u sein.

Beispiel 1[Bearbeiten]

Zerlege (F,0,6,3) mit 3=(0+6)/2

8	2	1	5	9	7	3

...

3	2	1	5	9	7	3

Beispiel 2[Bearbeiten]

Sei f[8]=5 das Pivot-Element

8	9	2	6	7	3	4	1	5

Suche von links aus das Element, welches kleiner als das Pivot-Element ist

8	9	2	6	7	3	4	1	5

Vertausche mit dem ersten größeren Element

2	9	8	6	7	3	4	1	5

Suche das nächste kleinere Element als die 5

2	9	8	6	7	3	4	1	5

Vertausche dieses mit dem zweiten größeren Element

2	3	8	6	7	9	4	1	5

Suche wieder das nächste kleinere Element

2	3	8	6	7	9	4	1	5

und vertausche dies mit dem dritt größeren Element

2	3	4	6	7	9	8	1	5

2	3	4	6	7	9	8	1	5

2	3	4	1	7	9	8	6	5

nun ist man rechts angekommen und hier wird nun das Pivot-Element getauscht

2	3	4	1	5	9	8	6	7

Von nun an steht das Pivot-Element an seiner finalen Position. Alle Elemente links vom Pivot-Element sind kleiner und alle auf der rechten Seite sind größer. Das bedeutet, dass nun ein rekursiver Abstieg für die Folgen

2	3	4	1

und

9	8	6	7

beginnen würde. Wenn das letzte Element wieder als Pivot-Element gewählt werden würde, dann hat die erste erste Folge nun das Pivot-Element 1 und in der zweiten Folge währe es das Element 7.

Alternative: Zerlegung mit while-schleifen[Bearbeiten]

Man wählt zuerst ein Pivotelement, beispielsweise das mittlere Element. Nun beginnt man von unten an und vergleicht die Einträge mit dem Pivot. Danach beginnt man von oben und vergleicht die Elemente mit dem Pivot. Wenn ein Element kleiner bzw. größer ist als das Pivot Element, dann wird dieses Element getauscht.

Analyse[Bearbeiten]

Theorem der Terminierung[Bearbeiten]

Das Theorem der Terminierung besagt, dass der Algorithmus quickSort für jede Eingabe int[]F nach endlicher Zeit terminiert.

Beweis[Bearbeiten]

In jedem rekursiven Aufruf von quickSort ist die Eingabelänge um mindestens 1 kleiner als vorher und die Rekursionsanfang ist erreicht wenn die Länge gleich 1 ist. In der Methode split gibt es nur eine for‐Schleife, dessen Zähler j in jedem Durchgang inkrementiert wird. Da u<o wird die for‐Schleife also nur endlich oft durchlaufen.

Theorem der Korrektheit[Bearbeiten]

Das Theorem der Korrektheit besagt, dass der Algorithmus quickSort das Problem des vergleichsbasierten Sortierend löst.

Beweis[Bearbeiten]

Die Korrektheit der Methode swap ist zunächst offensichtlich. Zeige nun, dass nach Aufruf pn=split(f,u,o,p) für u<o und $p\in [u,o]$ gilt:

f[p] wurde zu f[pn] verschoben

Dies ist klar (vorletzte Zeile der Methode split)

f[i] ≤ f[pn] für i=u,...,pn‐1

pn wird zu anfangs mit u initialisiert und immer dann inkrementiert, wenn die Position f[pn] durch ein Element, das kleiner/gleich dem Pivot‐Element ist, belegt wird.

f[i] > f[pn] für i=pn+1,...,o

Folgt aus der Beobachtung, dass in 2.) immer „genau dann“gilt. Beachte zudem, dass Element immer getauscht werden, also die Elemente im Array stets dieselben bleiben.

Die Korrektheit der Methode quickSort folgt nach Induktion nach der Länge von f (n=f.length):

  n=1: Der Algorithmus terminiert sofort und ein einelementiges Array ist stets sortiert
  n→n+1: Nach Korrektheit von split steht das Pivot‐Element an der richtigen Stelle und links und rechts stehen jeweils nur kleinere/größere Element. Die beiden rekursiven Aufrufe von quickSort erhalten jeweils ein Array, das echt kleiner als n+1 ist (mindestens das Pivot‐Element ist nicht mehr Teil des übergebenen Arrays). Nach Induktionsannahme folgt die Korrektheit von quickSort.

Theorem der Laufzeit[Bearbeiten]

Das Theorem der Laufzeit besagt, dass wenn als Pivot Element stets der Median des aktuell betrachteten Arrays gewählt wird, so hat der Algorithmus quickSort eine Laufzeit von $\Theta (n~log~n)$ .

Beweis[Bearbeiten]

Es gilt zunächst, dass split $\in \Theta (n)(mit~n=o-u)$ . Ausschlaggebend ist hier die for-Schleife, die genau n-mal durchlaufen wird. Gilt nach dem Aufruf von split stets pn=(u+o)/2 (dies ist gleichbedeutend damit, dass das Pivot‐Element stets der Median ist), so erhalten wir folgende Rekursionsgleichung für quickSort:

$T(n):=\left\{{\begin{array}{ll}\Theta (1)&{\text{für }}n\leq 1\\2T((n-1)/2)+\Theta (n)&sonst\end{array}}\right.$

Die ist fast dieselbe Rekursionsgleichung wie für MergeSort und es folgt $T(n)\in \Theta (n~log~n).$

Doch was ist, wenn die Voraussetzung des Theorems nicht erfüllt ist und wir ungleiche Rekursionsaufrufe haben?

Theorem der Laufzeit 2[Bearbeiten]

Das Theorem der Laufzeit besagt, dass der Algorithmus quickSort im schlechtesten Fall eine Laufzeit von $\Theta (n^{2})$ hat.

Beweis[Bearbeiten]

Angenommen, die Aufteilung erzeugt ein Teilarray mit Länge n‐1 und ein Teilarray mit Länge 0 (Pivot‐Element ist also immer Minimum oder Maximum), dann erhalten wir folgende Rekursionsgleichung für die Laufzeit:

$T(n):=\left\{{\begin{array}{ll}\Theta (1)&{\text{für }}n\leq 1\\2T(n-1)+\Theta (n)&sonst\end{array}}\right.$

Durch Induktionsbeweis kann leicht gezeigt werden, dass $T(n)\in \Theta (n^{2})$ . Dies ist auch tatsächlich der schlechteste Fall.

Für den mittleren Fall kann gezeigt werden, dass quickSort einen Aufwand von $\Theta (n~log~n)$ hat (wie im besten Fall), die in $\Theta$ versteckten Konstanten sind nur etwas größer.

Bemerkung[Bearbeiten]

Im Gegensatz zu MergeSort ist QuickSort durch die Vorgehensweise bei Vertauschungen instabil, d.h. relative Reihenfolge gleicher Schlüssel werden nicht notwendigerweise beibehalten.

Literatur[Bearbeiten]

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5.2.6 zu finden.

Untere Schranke[Bearbeiten]

Auf dieser Seite wird die untere Schranke für vergleichbare Sortierverfahren behandelt.

Eigenschaften der betrachteten Algorithmen[Bearbeiten]

Die Komplexität im Durchschnittsfall und im Schlechtesten Fall ist nie besser als n ‧ log n. Die Sortierung erfolgt ausschließlich durch Vergleich der Eingabe-Elemente (comparison sorts), es handelt sich somit um vergleichsorientierte Sortierverfahren. Nun zeigen wir, dass n ‧ log n Vergleiche eine untere Schranke für „Comparison Sort“-Algorithmen ist. Dies heißt dann, dass Sortieralgorithmen mit Komplexität (schlechtester Fall) von n ‧ log n (z.B. MergeSort) asymptotisch optimal sind.

Problembeschreibung[Bearbeiten]

Zuerst die Problembeschreibung. Als Eingabe haben wir $\langle a_{1},a_{2},...,a_{n}\rangle$ . Als Vergleichstests nehmen wir $a_{i}<a_{j},a_{i}\leq a_{j},a_{i}\equiv a_{j},a_{i}\geq a_{j},a_{i}>a_{j}$ . Als vereinfachte Annahmen nehmen wir an, dass es nur verschiedene Elemente gibt, somit entfällt $a_{i}\equiv a_{j}$ . Die restlichen Test liefern alle gleichwertige Informationen. Sie bestimmen die Reihenfolge von $a_{i}~und~a_{j}$ . Außerdem können sie und auf $a_{i}\leq a_{j}$ beschränken. Somit haben wir eine binäre Entscheidung und es gilt entweder $a_{i}\leq a_{j}~oder~a_{i}>a_{j}$

Entscheidungsbaum[Bearbeiten]

Eine beispielhafte Eingabe ist $a_{1}=6,a_{2}=8,a_{3}=5$ Die inneren Knoten vergleichen die Elemente $a_{i}~und~a_{j}$ . Es wird ein Test durchgeführt ob $a_{i}\leq a_{j}$ gilt oder nicht. Die Blätter sind Permutationen mit $\langle \pi (a_{1}),...,\pi (a_{n})\rangle$ Sortieren heißt das Finden eines Pfades von der Wurzel zu einem Blatt. An jedem internen Knoten erfolgt ein Vergleich und entsprechend wird links oder rechts weiter gesucht. Ist ein Blatt erreicht, dann hat der Sortieralgorithmus eine Ordnung und die Permutation der Elemente ist erstellt. Daraus lässt sich schlussfolgern, dass jeder Sortieralgorithmus jede Permutation der n Eingabe-Elemente erreichen muss (n!). Daraus folgt wiederum, dass es n! Blätter geben muss, die alle von der Wurzel erreichbar sind. Andernfalls kann er zwei unterschiedliche Eingaben nicht unterscheiden und liefert für beide dasselbe Ergebnis und eins davon muss falsch klassifiziert sein. Die Anzahl an Vergleichen im schlechtesten Fall ist die Pfadlänge von Wurzel bis Blatt, oder auch Höhe genannt.

Somit erhalten wir das Theorem, dass jeder vergleichsorientierte Sortieralgorithmus im schlechtesten Fall mindestens n*log n Versuche braucht.

Beweis[Bearbeiten]

Gegeben ist die Anzahl der Elemente n, h die Pfadlänge bzw. Höhe des Baums und b die Anzahl der Blätter. Jede Permutation muss in einem Blatt sein, das bedeutet $n!\leq b$ . Der Binärbaum hat die Höhe h und maximal $2^{h}$ Blätter, daraus folgt $n!\leq b\leq 2^{h}$ . Wenn man nun logarithmiert, erhält man

$h\geq log_{2}(n!)$

\sim n\cdot log_{2}(n)

(genauer~=\Omega (n\cdot log_{2}(n)))

Literatur[Bearbeiten]

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5.2.7 zu finden.