2.8 Zusammenfassung und Anmerkungen

In diesem Kapitel wurden die sechs bekanntesten Sortieralgorithmen vorgestellt und analysiert und mit Hilfe von objektorientierten Hamster-Programmen visualisiert.

Für genügend große Arrays ist QuickSort der im Mittel schnellste Sortieralgorithmus. Im unglücklichsten Fall kann jedoch MergeSort schneller sein. Für den Fall, dass das Array schon gut vorsortiert ist, sind InsertionSort und BubbleSort schnellere Alternativen.

ShellSort und QuickSort sind nicht stabil, die anderen vier Algorithmen sind stabil. MergeSort ist der einzige der vorgestellten Algorithmen, der nicht in-place ist.

Zahlreiche weitere Informationen zu Sortieralgorithmen finden Sie im Web, z.B. unter

• http://de.wikipedia.org/wiki/Sortieralgorithmus
• http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/sortalgo.htm
• http://www.sortieralgorithmen.de

2.8.1 Sortieren von Objekten

In den obigen Abschnitten werden die Sortieralgorithmen vorgestellt, indem Arrays mit int-Werten sortiert werden. Sie funktionieren jedoch auch zum Sortieren von Objekten beliebiger Klassen, wenn ein Schlüssel festgelegt und eine totale Ordnung auf dem Schlüssel definiert wird.

Zu diesem Zweck stellt Java bereits ein vordefiniertes Interface zur Verfügung, das Interface Comparable. Das Interface hat folgende Gestalt:

public interface Comparable {
  public int compareTo(Object o);
}

Wenn Sie Objekte einer bestimmten Klasse sortieren möchten, lassen Sie diese Klasse das Interface Comparable implementieren. Die Methode compareTo sollte dabei folgendermaßen implementiert werden:

• Sie liefert einen negativen Wert, wenn der Schlüssel des Objektes, für das die Methode aufgerufen wird, kleiner ist als der Schlüssel des als Parameter übergebenen Objektes.
• Sie liefert den Wert 0, wenn der Schlüssel des Objektes, für das die Methode aufgerufen wird, gleich dem Schlüssel des als Parameter übergebenen Objektes ist.
• Sie liefert einen positiven Wert, wenn der Schlüssel des Objektes, für das die Methode aufgerufen wird, größer ist als der Schlüssel des als Parameter übergebenen Objektes.

Bspw. könnte eine Klasse Person, bei der Personen nach ihrem Alter sortiert werden sollen, folgendermaßen definiert werden:

public class Person implements Comparable {
  String name;
  int alter;
  ...
  public int compareTo(Object o) {
    Person anderePerson = (Person)o;
    return this.alter - anderePerson.alter;
  }
}

Bei den Sortieralgorithmen ist folgendes anzupassen. Zunächst wird das Interface SortierAlgorithmus geändert. Sortiert werden sollen nicht mehr Arrays mit int-Werten, sondern Arrays mit Comparable-Objekten:

public interface SortierAlgorithmus {
  // sortiert das Array in aufsteigender Reihenfolge
  public void sortiere(Comparable[] array);
}

Weiterhin müssen die Vergleiche der Array-Elemente ($<$, $<=$, $>$, $>=$, $==$ und $!=$) innerhalb der einzelnen Algorithmen ersetzt werden durch entsprechende Aufrufe der compareTo-Methode. Dies sei am SelectionSort-Algorithmus beispielhaft illustiert:

public class SelectionSort implements SortierAlgorithmus {

  public void selection(Comparable[] array) {
    for (int aktIndex = 0; aktIndex < array.length - 1; aktIndex++) {
      int minIndex = aktIndex;
      for (int suchIndex = aktIndex+1; 
           suchIndex < array.length; 
           suchIndex++) {
        if (array[suchIndex].compareTo(array[minIndex]) < 0) {
          minIndex = suchIndex;
        }
      }
      Comparable speicher = array[aktIndex];
      array[aktIndex] = array[minIndex];
      array[minIndex] = speicher;
    }
  }
}

2.8.2 Sortieren von Zeichenketten

Zeichenketten sind in Java Objekte der vordefinierten Klasse String. Diese implementiert (glücklicherweise) das im vorherigen Abschnitt vorgestellte Interface Comparable, stellt also die Methode compareTo zur Verfügung. Verglichen werden dabei paarweise die entsprechenden Zeichen, und zwar gemäß der lexikographischen Ordnung^2.3.