Zwischenbemerkungen

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

Einordnung der elementaren Sortierverfahren

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

Eigenschaften

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

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

 

public class MyObject implements Comparable {. . .}

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

Interne Hilfsmethoden

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

 

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