Kapitel 4: Sortieren

1. Sortierprobleme

1.1 Motivation des Sortierens

Sortieralgorithmen spielen eine zentrale Rolle in der Informatik und im täglichen Leben. Viele Anwendungen erfordern eine geordnete Datenstruktur, um effizient arbeiten zu können. Beispiele für sortierwürdige Daten sind:

• Telefonbücher – Sortierung nach Nachnamen für schnelle Suche.
• Patientendateien – Sortierung nach Name oder Dringlichkeit.
• Preis- und Produktlisten – Sortierung nach Preis, Kategorie oder Beliebtheit.
• Suchergebnisse – Ordnung nach Relevanz, Datum oder Nutzerinteressen.

Ziele des Sortierens

Das Sortieren von Daten hat mehrere zentrale Ziele:

• Effiziente Suche: Sortierte Daten ermöglichen schnellere Suchvorgänge, insbesondere mit Algorithmen wie der binären Suche.
• Datenkonsistenz und Synchronisation: Sortierung hilft bei der konsistenten Bearbeitung großer Datenmengen.
• Optimierung der Rechenzeit: Studien zeigen, dass mehr als 25 % der kommerziellen Rechenzeit für Sortiervorgänge verwendet werden ([Ottmann und Widmayer, 2012]).

Eine wichtige Beobachtung ist, dass nicht immer alle Attribute eines Objekts für die Sortierung relevant sind. Beispielsweise können Produktlisten nach Preis geordnet sein, enthalten aber viele weitere Merkmale wie Hersteller oder Bewertungen, die für die Reihenfolge keine Rolle spielen.

1.2 Definition von Sortierproblemen

Übliche Formulierung:

• Gegeben ist eine Menge von Sätzen (Datenobjekten).
• Jeder Satz enthält einen Schlüssel, nach dem sortiert wird.
• Zusätzlich zu diesem Schlüssel können Sätze weitere Attribute enthalten, die für die Sortierung nicht relevant sind.
• Zwischen den Schlüsseln ist eine Ordnungsrelation $<$ oder $\le$ definiert, sodass je zwei Elemente vergleichbar sind.

Annahmen zur Schlüsselstruktur:

Falls nicht anders angegeben, werden üblicherweise folgende Annahmen für Schlüssel getroffen:

• Ganzzahlige Schlüssel – oder solche, die auf ganze Zahlen abgebildet werden können.
• Typische Beispiele für numerische Schlüssel:
  • Artikelnummern
  • Hausnummern
  • Personalnummern
  • Schulnoten
• Alternative Schlüsselformate:
  • Alphabetische Reihenfolge – beispielsweise für Namen in einer Kundenliste.
  • Lexikografische Ordnung – etwa bei der Sortierung von Wörtern oder Dateinamen.

Ein häufiges Zusatzkriterium ist das Fehlen von Duplikaten, d. h. jede betrachtete Datenmenge enthält eindeutige Schlüssel. Falls Duplikate zugelassen werden, ergeben sich zusätzliche Anforderungen an die Sortierverfahren, insbesondere im Hinblick auf die Stabilität eines Sortieralgorithmus (d. h. ob die ursprüngliche Reihenfolge gleicher Schlüssel erhalten bleibt).

1.3 Herausforderungen bei der Sortierung

Sortierprobleme sind vielfältig, und es gibt verschiedene Herausforderungen, die eine effiziente Lösung erfordern:

• Große Datenmengen: Bei Millionen oder Milliarden von Elementen ist eine effiziente Laufzeit entscheidend.
• Dynamische Daten: In vielen Anwendungen ändern sich Daten kontinuierlich, sodass ein effizientes Neusortieren erforderlich ist.
• Mehrere Sortierkriterien: Manchmal sind mehrere Attribute für die Sortierung relevant, z. B. Produkte zuerst nach Kategorie und dann nach Preis zu ordnen.
• Ressourcenbeschränkungen: Manche Sortieralgorithmen sind speicherintensiv, was insbesondere bei eingebetteten Systemen oder datenintensiven Anwendungen eine Rolle spielt.

2. Mathematische Grundlagen

2.1 Ordnungsrelationen

Definition: Eine Relation $\le$ auf einer Menge $M$ heißt (schwache) Totalordnung (oder lineare Ordnung), wenn sie folgende Eigenschaften erfüllt:

• Reflexivität: Für alle $x\in M$ gilt $x\le x$.
• Antisymmetrie: Für alle $x,y\in M$ gilt: Wenn $x\le y$ und $y\le x$, dann muss $x=y$ sein.
• Transitivität: Für alle $x,y,z\in M$ gilt: Aus $x\le y$ und $y\le z$ folgt $x\le z$.
• Totalität: Für alle $x,y\in M$ gilt: $x\le y$ oder $y\le x$.

2.2 Permutationen

Definition: Eine Permutation ist eine bijektive Abbildung einer Menge auf sich selbst, also eine Umordnung der Elemente.

• Anwendung im Sortieren: Beim Sortieren soll eine Permutation gefunden werden, die die Elemente eines Arrays so anordnet,
  dass für alle Indizes
  $0\le i<j<n$ gilt: $a[i]\le a[j]$

Hinweis: Oft wird das Bild einer Permutation – also die neu geordnete Folge – ebenfalls als Permutation bezeichnet.

2.3 Inversionszahl

• Definition: Gegeben eine Folge $a=(a_0,a_1,\dots ,a_{n-1})$ aus einem total geordneten Universum.
  Dann ist die Inversionszahl $\mathrm{inv}(a)$ definiert als die Anzahl der Paare $(a_i,a_j)$, für die gilt: $i<j\text{und}{a}_i>a_j.$

Beobachtungen:

• $\mathrm{inv}(a)=0$, falls die Folge sortiert ist.
• Die maximale Inversionszahl beträgt $\frac{n(n-1)}{2}$, was in der Größenordnung $\mathrm{\Theta }(n^2)$ liegt.
• Die Überprüfung aller Paare auf Inversionen hat eine Laufzeit von $O(n^2)$.
• Die Inversionszahl dient als Maß für die Vorsortiertheit einer Folge: Je niedriger der Wert, desto näher ist die Folge an einer vollständig sortierten Reihenfolge.

2.4 Sortierprobleme: Definitionsvarianten

Gegeben:
Eine Menge $U$ von $n$ Elementen aus einem total geordneten Universum und deren Speicherung in einem Feld $A$ der Länge $n$.
Gesucht:
Eine Permutation der Elemente in $A$, sodass für alle Indizes $0\le i<j<n$ die Ordnungsbedingung erfüllt ist:
$a[i]\le a[j].$

INFO

Es wird oft angenommen, dass keine Duplikate in der Schlüsselmenge vorhanden sind.

3. Überprüfung der Sortiertheit

Grundidee vieler Sortierverfahren:
Solange es Indizes $i$ und $j$ gibt, die die Ordnungsbedingung $a[i]\le a[j]$ (für $i<j$) verletzen,
werden die Elemente $a[i]$ und $a[j]$ vertauscht.
Dieses Vorgehen führt schrittweise zur vollständigen Sortierung der Elemente.

Java Code für Sortiertheit

boolean istSortiert(T[] a) {
    for (int i = 0 ; i <= a.length – 2 ; i++) {
        if (a[i] > a[i + 1]) return false;
    }
    return true;
}

4. Sortieralgorithmen

Eine kurze Code-Vorstellung der ersten drei Algorithmen

bubbleSort

public static void bubbleSort(int[] a) {
    boolean swapped;
    do {
        swapped = false;
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] > a[i + 1]) { // Falls die Reihenfolge falsch ist
                swap(a, i, i + 1); // Vertausche Elemente
                swapped = true;
            }
        }
    } while (swapped); // Wiederhole, bis keine Vertauschung mehr erfolgt
}

selectionSort

public static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int minElementIndex = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[minElementIndex]) {
                minElementIndex = j;
            }
        }
        swap(a, i, minElementIndex);
    }
}

insertionSort

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int toInsert = a[i];
        int decreasingIndex = i - 1;
        while (decreasingIndex >= 0 && toInsert < a[decreasingIndex]) {
            a[decreasingIndex + 1] = a[decreasingIndex];
            decreasingIndex--;
        }
        a[decreasingIndex + 1] = toInsert;
    }
}

4.1 BubbleSort

Prinzip:
BubbleSort basiert auf der Idee, dass größere Werte durch paarweisen Vergleich und Vertauschung nach und nach ans Ende der Liste "aufsteigen" – ähnlich wie Luftblasen in Wasser.

Implementation in Java:

Algorithmus:

1. Durchlaufe das Array mehrfach.
2. Vergleiche jeweils zwei benachbarte Elemente:
   • Falls das linke größer als das rechte ist, vertausche sie.
3. Wiederhole diesen Vorgang, bis keine Vertauschungen mehr erforderlich sind.

public static void bubbleSort(int[] a) {
    boolean swapped;
    do {
        swapped = false;
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] > a[i + 1]) { // Falls die Reihenfolge falsch ist
                swap(a, i, i + 1); // Vertausche Elemente
                swapped = true;
            }
        }
    } while (swapped); // Wiederhole, bis keine Vertauschung mehr erfolgt
}

Laufzeitanalyse:

• Im schlechtesten Fall muss der Algorithmus das Array $n-1$ Mal durchlaufen, wobei die innere Schleife jeweils $n-i-1$ Vergleiche ausführt: $(n-1)+(n-2)+\cdots +2+1=\frac{(n-1)\cdot n}{2}\in O(n^2).$
• Bester Fall: Wenn das Array bereits sortiert ist, reicht eine einzige Iteration $O(n)$.

4.2 SelectionSort

Prinzip:
SelectionSort findet in jedem Durchlauf das kleinste (oder größte) Element im unsortierten Teil der Liste und tauscht es an die richtige Position.

Implementation in Java:

Algorithmus:

1. Gehe durch das Array und finde das kleinste Element.
2. Tausche es mit dem ersten Element.
3. Wiederhole den Vorgang für den restlichen unsortierten Teil des Arrays.

public static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int minElementIndex = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[minElementIndex]) {
                minElementIndex = j;
            }
        }
        swap(a, i, minElementIndex);
    }
}

Laufzeitanalyse:

• Da immer das gesamte unsortierte Feld durchsucht werden muss, beträgt die Anzahl der Vergleiche:
  $(n-1)+(n-2)+\cdots +1=\frac{(n-1)\cdot n}{2}\in O(n^2).$
• Die Anzahl der Vertauschungen ist jedoch nur $O(n)$, da maximal $n-1$ Vertauschungen erfolgen.

4.3 InsertionSort

Prinzip:
InsertionSort baut eine sortierte Teilliste auf, indem Elemente einzeln an die richtige Stelle eingefügt werden.

Implementation in Java:

Algorithmus:

1. Beginne mit dem zweiten Element.
2. Verschiebe alle größeren Elemente nach rechts, um Platz zu machen.
3. Füge das aktuelle Element an die richtige Stelle ein.

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int toInsert = a[i];
        int decreasingIndex = i - 1;
        while (decreasingIndex >= 0 && toInsert < a[decreasingIndex]) {
            a[decreasingIndex + 1] = a[decreasingIndex];
            decreasingIndex--;
        }
        a[decreasingIndex + 1] = toInsert;
    }
}

Laufzeitanalyse:

• Best-Case (vorsortierte Liste): $O(n)$.
• Worst-Case (umgekehrte Reihenfolge): $O(n^2)$, da jedes Element bis zum Anfang verschoben werden muss.

Verbesserung: Statt eine lineare Suche für den Einfügepunkt zu nutzen, kann eine binäre Suche verwendet werden, um die Anzahl der Vergleiche auf $O(n\log n)$ zu reduzieren, aber die Anzahl der Verschiebungen bleibt $O(n^2)$.

4.3 MergeSort

Der MergeSort-Algorithmus wird anhand des Divide-and-Conquer-Prinzips erklärt, inklusive der Beschreibung der Rekursionsanker, eines Code-Gerüsts und der Komplexitätsanalyse mittels Rekursionsbaum.

4.4 Quicksort

In diesem Teil wird das Quicksort-Verfahren erläutert, wobei die Bedeutung von Pivot-Element, Partitionierung und rekursiver Implementierung (in-place mit $O(1)$ Zusatzspeicher) sowie die Worst-Case-Analyse im Fokus stehen.

5. Komplexitätsanalysen

Dieser Abschnitt widmet sich der präzisen Ermittlung der $O$-Komplexitätsklassen der vorgestellten Verfahren (z. B. 2-Wege- und 3-Wege-MergeSort, pivot-ideales Quicksort, Median-Find, Binäre Suche, Türme von Hanoi) mithilfe von Rekursionsbaum-Methoden und Induktionsbeweisen.

6. Zusammenfassung und Ausblick

Abschließend werden die zentralen Erkenntnisse des Kapitels zusammengefasst und ein Ausblick auf weiterführende Themen im Bereich der Sortierung und algorithmischen Optimierung gegeben.