Sortieren

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

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

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

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

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

Java Stub

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

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

public interface Sort {

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

Ausblick

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

Literatur

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.