Einfache Sortierverfahren

Wir beschäftigen uns in dieser Unit mit einfachen aber grundlegenden Sortierverfahren. Viele aktuell eingesetzte Sortierverfahren (z. B. Timsort, das Standardsortierverfahren von Python) sind vom Prinzip her nur Kombinationen aus diesen einfachen Ideen.

Es werden drei absolute Klassiker unter den Sortierverfahren betrachtet: Bubblesort, Selectionsort und Insertionsort. Diese werden im Folgenden am Beispiel des Sortierens von Spielkarten vorgestellt.

Bevor wir beginnen, klären wir noch, welches Problem wir lösen wollen. Das Sortierproblem ist wie folgt definiert:
Gegeben: Ein Array \(A\), welches \(n\) vergleichbare Elemente enthält.
Aufgabe: Erzeuge ein aufsteigend sortiertes Array, welches dieselben Elemente wie \(A\) enthält.

Als Beispiel werden wir das Sortieren von Spielkarten betrachten. Dabei ist unser Array einfach eine Reihe von Spielkarten, die vor uns auf dem Tisch liegt. Unsere Eingabe sieht dabei wie folgt aus:

Wir wollen aufsteigend sortieren und halten uns dabei an die bekannten Kartenwertigkeiten von z. B. Skat, d. h. Karo \(\lt\) Herz \(\lt\) Pik \(\lt\) Kreuz und innerhalb der Farben jeweils 7 \(\lt\) 8 \(\lt\) 9 \(\lt\) 10 \(\lt\) Bube \(\lt\) Dame \(\lt\) König \(\lt\) Ass.

Bubblesort

Die Idee von Bubblesort ist im Prinzip das sukzessive Vertauschen von Elementen, um diese in die richtige Richtung zu bewegen. Dabei bewegen sich die größeren Elemente nach und nach von links nach rechts in der Folge. Sie steigen somit ähnlich wie Blasen im Wasser nach oben, daher auch der Name Bubblesort.

Bei Bubblesort wird jeweils in Runden für jedes benachbarte Paar von Elementen getestet, ob diese vertauscht werden müssen. Sobald mindestens eine Vertauschung nötig war, dann beginnt eine neue Runde. Falls nicht, dann ist die Folge bereits korrekt sortiert.

Wieder betrachten wir, was für unsere Beispieleingabe passiert. Wir beginnen mit exakt derselben Instanz:

Als Erstes werden die beiden linkesten Karten verglichen und vertauscht. Danach erfolgt der Vergleich der zweiten und dritten Karte:

Wieder wird getauscht, danach werden die dritte und vierte Karte verglichen usw. Die erste Runde endet mit dem Vergleich der letzten beiden Karten:

Nach der Vertauschung der letzten beiden Karten muss die größte Karte ganz rechts stehen. Dies gilt, da wir ja die jeweils größere Karte immer nach rechts getauscht haben. Folglich haben wir nach der ersten Runde einen korrekt soriterten Bereich der Größe \(1\) ganz rechts. In der nächsten Runde können wir deshalb die letzte Karte vernachlässigen. Wir wissen ja bereits, dass dort die größte Karte korrekt platziert wurde.

Nach der zweiten Runde ist die zweitgrößte Karte auf die vorletzte Position aufgestiegen und somit haben wir einen korrekt sortierten Bereich der Größe \(2\) am rechten Rand der Folge hergestellt.

Analog, nach der dritten Runde ist der sortierte Bereich weiter gewachsen.

In der folgenden Runde tritt keine Vertauschung mehr auf und somit wird abgebrochen.

Betrachten wir den Pseudocode von Bubblesort (Achtung, die Indizierung von Array \(A\) beginnt bei \(0\)):

function BubbleSort(A) {
    newRound := TRUE;
    for i := n-1 downto 1 do {
      if newRound then {
         newRound := FALSE;
         for j := 0 to i-1 do {
             if A[j] > A[j+1] then {
                temp := A[j];
                A[j] := A[j+1];
                A[j+1] := temp;
                newRound := TRUE;
             }
         }
      }
      else break 
    }
}

Korrektheit von Bubblesort

Hier die Beweisidee:

Aus den obigen Ideen den vollständigen Beweis zu formulieren, ist eine gute Übungsaufgabe!

Laufzeitanalyse von Bubblesort

Ein Blick auf den Pseudocode verrät uns, dass die äußere for-Schleife auf jeder Instanz mit \(n\) Elementen mindestens einmal ausgeführt wird. Jeder Durchlauf der äußeren for-Schleife bewirkt immer einen kompletten Durchlauf der inneren for-Schleife, wobei die Anzahl der Durchläufe der inneren Schleife mit der Anzahl der Durchläufe der äußeren Schleife abnimmt. Genauer gilt, dass im \(i\)-ten Durchlauf der äußeren Schleife die innere Schleife genau \(n-i\)-mal durchlaufen wird.

Im besten Fall (Bestcase), falls die Instanz bereits aufsteigend sortiert ist, dann wird die äußere for-Schleife nur genau ein mal durchlaufen. Die innere for-Schleife läuft dabei genau \(n-1\)-mal und hat pro Durchlauf konstante Kosten. Dies ergibt insgesamt Kosten von \(\Theta(n)\).

Im schlimmsten Fall (Worstcase), falls die Instanz zu Beginn umgekehrt, d. h. absteigend, sortiert ist, dann erfolgen im \(i\)-ten Durchlauf der äußeren for-Schleife genau \(n-i\) viele Durchläufe der inneren for-Schleife mit jeweils konstanten Kosten. Der \(i\)-te Durchlauf der äußeren for-Schleife kostet somit \(c\cdot (n-i)\), wobei \(c\) hier eine Konstante ist. Insgesamt, über alle Durchläufe der äußeren for-Schleife aufsummiert, ergeben sich Kosten von \[\sum_{i=n-1}^{1}c\cdot (n-i) = c \cdot \sum_{i=n-1}^{1}(n-i) = c \cdot \sum_{i=1}^{n-1} i = c \cdot \frac{n(n-1)}{2} \in \Theta(n^2).\]

Selectionsort

Selectionsort basiert auf einer iterativen Suche nach dem Minimum. Dabei wird zu Beginn das kleinste Element bestimmt und an die erste Stelle getauscht. Danach wird im restlichen Array wieder das Minimum gesucht und an die zweite Stelle getauscht usw. Dieser Prozess bricht ab, sobald es nur noch ein Element im restlichen Array gibt.

Wieder betrachten wir, was auf unserer Beispielinstanz passiert. Zu Beginn wird das Minimum der Instanz ermittelt (blau markiert).

Das Minimum wird direkt an die erste Stelle getauscht und somit erhalten wir einen korrekt sortierten Bereich der Größe \(1\) am linken Ende der Folge. Nun wird das Minimum unter allen anderen Elementen bestimmt.

Nach dem Tausch an die zweite Position wird wiederum das Minimum unter den restlichen Karten (d. h. Karten 3 bis 8) bestimmt.

Nach dem Tausch an die dritte Position wird das Minimum unter Karten 4 bis 8 bestimmt.

Nach dem Tausch an die vierte Position wird das Minimum unter Karten 5 bis 8 bestimmt.

Es wird getauscht und das Minimum unter Karten 6 bis 8 bestimmt.

Wieder wird getauscht, danach das Minimum unter Karten 7 bis 8 bestimmt.

Nach einem weiteren Tausch sind wir fertig, da im restlichen Array nur noch ein Element (nämlich das Maximum der Instanz) übrig ist und dieses auch bereits an der richtigen Stelle steht.

Betrachten wir den Pseudocode von Selectionsort (Achtung, die Indizierung von Array \(A\) beginnt bei \(0\)):

function SelectionSort(A) {
    for i := 0 to n-2 do {
         currentMinIndex := i;
         for j := i+1 to n-1 do {
             if A[currMinIndex] > A[j] then currMinIndex := j;
         }
         temp := A[i];
         A[i] := A[currMinIndex];
         A[currMinIndex] := temp;
      }
 }

Korrektheit von Selectionsort

Die Korrektheit folgt aus der Invariante, dass nach Runde \(i\) bei Selectionsort die \(i\) kleinsten Elemente aufsteigend sortiert an den Positonen \(0\) bis \(i-1\) im (\(0\)-indizierten) Array stehen.

Die Invariante kann leicht per Induktion gezeigt werden:
Induktionsanfang: In der ersten Runde von Selectionsort wird das Minimum aus allen Elementen im Array ermittelt und an Indexposition \(0\) getauscht.
Für den Induktionsschritt nehmen wir an, dass nach der \(i\)-ten Runde die \(i\) kleinsten Elemente aufsteigend sortiert an den Positionen \(0\) bis \(i-1\) stehen. Selectionsort bestimmt dann aus den verbleibenden Elementen, d. h. den Elementen an Positonen \(i\) bis \(n-1\), das Minimum und tauscht es an die Position \(i\). Nach Annahme muss dieses Element größer (oder gleich) als jedes Element an Positionen \(0\) bis \(i-1\) sein und da es das Minimum der Elemente von Postionen \(i\) bis \(n-1\) ist, muss es folglich das \(i+1\)-kleinste Element der Gesamtfolge sein. Nach dem Tausch befinden sich somit die \(i+1\) kleinsten Elemente aufsteigend sortiert an den Postionen \(0\) bis \(i\) im Array. \(\Box\)

Laufzeitanalyse von Selectionsort

Die äußere for-Schleife wird auf jeder Instanz mit \(n\) Elementen genau \(n-1\)-mal durchlaufen und jedes Mal findet eine Vertauschung statt. Jeder Durchlauf der äußeren for-Schleife bewirkt immer einen kompletten Durchlauf der inneren for-Schleife. Für die Anzahl der Durchläufe der inneren Schleife gilt dabei, dass im \(i\)-ten Durchlauf der äußeren Schleife die innere Schleife genau \(n-i\)-mal durchlaufen wird.

Somit entsehen für jede Instanz mit \(n\) Elementen genau dieselben Kosten. Der \(i\)-te Durchlauf der äußeren for-Schleife kostet somit auf jeder Instanz \(c\cdot (n-i)\), wobei \(c\) hier eine Konstante ist. Insgesamt, über alle Durchläufe der äußeren for-Schleife aufsummiert, ergeben sich Kosten von \[\sum_{i=1}^{n-1}c\cdot (n-i) = c \cdot \sum_{i=1}^{n-1}(n-i) = c \cdot \sum_{i=1}^{n-1} i = c \cdot \frac{n(n-1)}{2} \in \Theta(n^2).\]

Insertionsort

Insertionsort arbeitet wie folgt: Vergleiche die von links her ersten beiden Karten und tauschen die kleinere nach links. Damit entsteht ein sortierter Bereich, welcher zwei Karten umfasst. Füge jede weitere Karte an die entsprechende Stelle im bereits sortierten Bereich ein. Hierzu vergleiche jeweils von rechts nach links mit allen Karten im aktuellen sortierten Bereich und vertausche, falls nötig. Falls keine Vertauschung erfolgt ist, dann ist die aktuelle Karte korrekt einsortiert.

Wir betrachten, was an unserem Beispiel passiert.
Zu Beginn haben wir einen aktuell sortieren Bereich der Größe \(1\) vorliegen, welcher nur aus der linkesten Karte besteht. Der jeweils aktuell sortierte Bereich ist grün markiert. Als ersten werden die ersten beiden Karten verglichen:

Es muss getauscht werden. Danach haben wir einen aktuell sortierten Bereich der Größe \(2\) und in diesen wird nun die dritte Karte von rechts her eingeordnet. D. h., als Nächstes wird Pik 10 mit Karo Ass verglichen:

Es wird getauscht und danach folgt der Vergleich mit der linkesten Karte.

Danach haben wir den aktuell sortierten Bereich auf Größe \(3\) erweitert:

Nun wird die vierte Karte nach dem selben Prinzip einsortiert. Dabei erfolgen nur die Vergleiche Pik 10 vs. Herz 7 und Herz 7 vs. Karo Ass. Danach erhalten wir:

Die nächsten drei Karten werden mit jeweils einem Vergleich einsortiert und danach haben wir folgende Situation:

Nun wird noch die letzte Karte einsortiert. Nach den Vergleichen Kreuz 7 vs. Kreuz Ass, Kreuz 7 vs. Kreuz König und Kreuz 7 vs. Kreuz 9 haben wir:

Fazit: Insertionsort vergrößert nach und nach den sortierten Bereich, in dem es die korrekte Position für das jeweils neu einzufügende Element von rechts her mittels linearer Suche ermittelt.

Betrachten wir den Pseudocode von Insertionsort (Achtung, die Indizierung von Array \(A\) beginnt bei \(0\)):

function InsertionSort(A){
    for i := 1 to  n-1 do{
      j := i;
      aktuellesElement := A[j];
      while A[j-1] > aktuellesElement and j > 0 do{
        A[j] := A[j-1];
        j := j-1;
      }
      A[j] := aktuellesElement;
    }
}

Korrektheit von Insertionsort

Übungsaufgabe. Analog zum Korrektheitsbeweis von Selectionsort.

Laufzeitanalyse von Insertionsort

Ein Blick auf den Pseudocode verrät uns, dass die for-Schleife auf jeder Instanz mit \(n\) Elementen genau \(n-1\)-mal durchläuft. Bei der while-Schleife hingegen hängt die Anzahl der Durchläufe davon ab, wie viele größere Elemente links vom aktuell betrachteten Element stehen.

Im besten Fall (Bestcase), falls die Instanz bereits aufsteigend sortiert ist, dann fällt pro Ausführung der while-Schleife nur genau ein Vergleich an. Somit hat in diesem Fall ein Durchlauf der for-Schleife nur konstante Kosten und wir haben insgesamt Kosten von \(\Theta(n)\).

Im schlimmsten Fall (Worstcase), falls die Instanz zu Beginn umgekehrt, d. h. absteigend, sortiert ist, dann erfolgen im \(i\)-ten Durchlauf der for-Schleife genau \(i\) viele Vergleiche und \(i\) viele Vertauschungen in der zugehörigen while-Schleife. Der \(i\)-te Durchlauf der for-Schleife kostet somit \(c\cdot i\), wobei \(c\) hier eine Konstante ist. Insgesamt, über alle Durchläufe der for-Schleife aufsummiert, ergeben sich Kosten von \[\sum_{i=1}^{n-1}c\cdot i = c \cdot \sum_{i=1}^{n-1}i = c \cdot \frac{n(n-1)}{2} \in \Theta(n^2).\]

Was haben wir gelernt?

1. Wir haben drei grundlegende, jedoch stark verschiedene Sortierverfahren kennengelernt, deren Korrektheit bewiesen und deren Laufzeit analysiert.
2. Alle betrachteten Verfahren verfolgen das Prinzip, dass eine anfangs kleine sortierte Teilfolge nach und nach zu einer größeren sortierten Teilfolge erweitert wird.
3. Insertionsort erreicht dies, indem neue Elemente in die bereits bestehende sortierte Teilfolge einsortiert werden.
4. Bubblesort vertauscht jeweils rundenweise alle benachbarten Elemente. Dabei steigen die großen Elemente ähnlich wie Blasen im Wasser nach oben. Somit bildet sich eine sortierte Teilfolge der größten Elemente und diese wird sukzessive erweitert, indem weitere kleinere Elemente zu dieser Folge aufsteigen.
5. Selectionsort sucht jeweils iterativ das Minimum der verbleibenden Elemente und tauscht dies an die kleinste noch verfügbare Position im Array.
6. Insertionsort und Bubblesort haben im besten Fall nur lineare Laufzeit und im schlimmsten Fall quadratische Laufzeit. Selectionsort hingegegen benötigt unabhängig von der Instanz immer quadratische Laufzeit.