Theoretische Informatik

2.1 Naive Sortieralgorithmen: SelectionSort und InsertionSort

Der erste Sortieralgorithmus, den wir kennenlernen werden, ist SelectionSort. Dieser sucht in einem Array das kleinste Element und verschiebt es an den Anfang (also auf Position 0). Dann wiederholen wir es auf dem Teil-Array mit Indizes 1 bis $n-1$. Hier ist eine Animation, die SelectionSort auf einem Array der Größe 7 illustriert (aber nicht zu Ende führt):

Am Anfang der $k$-ten Phase befinden sich in den ersten $k$ Positionen des Arrays die $k$ kleinsten, aufsteigend sortiert. In der $k$-ten Phase müssen wir das kleinste Element unter $A[k], A[k+1],\dots,A[n-1]$ finden und mit dem an Position $k$ vertauschen. In Pseudocode schaut das so aus:

selectionSort(array):
    for k = 0 to n-1:
        argmin := die Position des kleinsten Elements in A[k..n-1] 
        vertausche A[k] mit A[argmin] 
    return A

Demo. Wir testen SelectionSort mit der Datei german-50000.txt. Wir nicht am Ergebnis interessiert, sondern nur an der Laufzeit. Daher:

time java SelectionSort < german-50000.txt > /dev/null

Die Laufzeit schwankt von mal zu mal (je nachdem, ob ich währenddessen noch etwas Anderes am Computer mache), liegt aber ungefähr zwischen 20 und 40 Sekunden.

Übungsaufgabe Implementieren Sie SelectionSort in Java. Ich habe Ihnen bereits ein Code-Skelett SelectionSort.java geschrieben, welches die Daten zeilenweise einliest und in einem Comparable[] array speichert. Sie müssen also nur die Funktion public static void sort (Comparable[] array) implementieren.

Hinweis. Achten Sie besonders auf dei Zeile 3 in meinem Pseudocode. Hier müssen Sie in Java eine weitere Schleife schreiben, die das Argmin bestimmt.

Theoretische Analyse von Sortieralgorithmen

Für Sortieralgorithmen haben wir ein Kriterium für deren Effizienz, das nicht von der Tageslaune des Computers abhängt: die Anzahl der Vergleiche; wie oft Sie also compareTo aufgerufen haben. Wenn also Ihre Vergleichsoperation an sich recht teuer ist, dann ist dies ein sehr guter Maßstab. Oft sind die Vergleichsoperationen aber relativ billig (wenn es sich bei den Daten zum Beispiel um int oder float handelt), und dann spielen andere Phänomene eine Rolle; dann kann es vorkommen, dass ein Algorithmus, der etwas mehr Vergleiche tätigt, denoch schneller ist. Die Anzahl der Vergleiche ist aber auch in diesem Fall ein zumindest anständiger Maßstab.

Übungsaufgabe Wieviele Vergleiche benötigen Sie, um in Zeile 3 der Pseudocodes das Argmin zu bestimmen?

Leiten Sie eine Formel für die Gesamtzahl der Vergleichsoperationen her, die SelectionSort auf einem Array mit $n$ Elementen tätigt.

InsertionSort

Der zweite Algorithmus, den wir untersuchen, ist InsertionSort. Er ist dem SelectionSort sehr ähnlich, allerdings versucht er pro Phase nicht, das Minimum in array[k..n-1] zu finden, sondern nimmt das Element array[k] und verschiebt es nach links, bis es seinen korrekten Platz gefunden hat und array[0..k] wieder sortiert ist. Hier sehen Sie eine Animation:

Ähnlich wie SelectionSort gilt auch bei InsertionSort, dass am Anfang von Phase $k$ die ersten $k$ Elemente des Arrays sortiert sind. Allerdings sind diese nicht notwenidgerweise die kleinsten $k$ Elemente des gesamten Arrays, sondern sind identisch mit den ersten $k$ Elementen des unsortierten Arrays. In Pseudocode können wir InsertionSort folgendermaßen darstellen:

insertionSort(array):                        
  for k = 0 to n-1:
      while k > 0 and array[k] < array[k-1]
          vertausche array[k] mit array[k-1]
  return array

Demo. Wir testen InsertionSort mit der Datei german-50000.txt:

time java SelectionSort < german-50000.txt > /dev/null

Die Laufzeit liegt auf meinem Rechner bei ungefähr 26 Sekunden. Es ist also vergleichbar mit SelectionSort.

Übungsaufgabe Wieviele Vergleichsoperationen führt InsertionSort aus auf einem Array der Größe $n$? Hinweis. Die Antwort ist nicht für jedes Input-Array gleich. Finden Sie ein bestes und ein schlechtestes Array und geben Sie für beide Fälle die Anzahl der Vergleichsoperationen als Funktion in $n$ an.

Übungsaufgabe Implementieren Sie InsertionSort in Java. Nehmen Sie wieder SelectionSort.java als Vorlage, ändern den Namen und implementieren die Funktion sort.

Laufzeitanalyse

Sie haben vielleicht bemerkt, dass die Anzahl der Vergleichsoperationen, die SelectionSort ausführt, in jedem Fall $$ 1 + 2 + \cdots + n-1 = {n \choose 2} = \frac{n(n-1)}{2} $$ ist. Für InsertionSort ist sie im besten Fall $n-1$ (falls das Array bereits aufsteigend sortiert ist), im schlechtesten Fall aber auch ${n \choose 2}$, also genau wie bei SelectionSort. Falls Ihnen dieser Ausdruck nicht so geläufig ist, können wir ihn so abschätzen: \begin{align} {n \choose 2} & = \frac{(n(n-1))}{2} = \frac{n^2}{2} - \frac{n}{2} \\ & = \frac{n^2}{2} - \textnormal{etwas, das deutlich kleiner ist }\\ & \approx \frac{n^2}{2} \\ & = n^2 \times \textnormal{ etwas}. \end{align}

In der Vorlesung Algorithmen und Komplexität werden Sie mehr im Detail lernen, wie man solche Abschätzungen mathematisch rigoros durchführt. Hier sei nur gesagt: das etwas ist in diesem Fall $\frac{1}{2}$; für die theoretische Laufzeitanalyse ist das aber nicht so relevant, da Sie z.B. beim Vergleich von verschiedenen Laptops (meiner: alt; Ihrer: neu) feststellen werden, dass die Geschwindigkeiten sich eh um einen gewissen Faktor unterscheiden; es hat also durchaus seine Berechtigung, den Faktor etwas erstmal zu ignorieren.

Einen ähnlichen, vielleicht intuitiveren Blickwinkel auf die Laufzeit eröffnet folgende Frage: Wenn ich die Größe meines Arrays verdopple, wie ändert sich dann die Laufzeit? Wenn wir dies für die Anzahl der Vergleichsoperationen, also${n \choose 2}$, gegenüberstellen, bekommen wir folgende Rechnung:

\begin{align*} \frac{2n \choose 2}{n \choose 2} & = \frac{\frac{2n (2n-1)}{2}}{\frac{n (n-1)}{2}} = \frac{2n (2n-1)}{n (n-1)} = 4 \cdot \frac{n - \frac{1}{2}}{n-1} \\ & = 4 \cdot \frac{n - 1 + \frac{1}{2}}{n-1} \\ & = 4 \cdot \left(1 + \frac{1}{2n-2}\right) \ . \end{align*}

Für großes $n$ konvergiert der Wert in der Klammer gegen $1$. Wir können also sagen: Für ein doppelt so großes Array brauchen SelectionSort und InsertionSort ungefähr viermal so lange. Dies ist natürlich nicht zufriedenstellend. Doppelt so lange klänge vernünftig, da könnten wir uns nicht beschweren. Aber viermal so lange hieße ja, dass es bei 100.000 Wörtern auf meinem Rechner eine Minute, bei 200.000 Wörtern bereits vier Minuten dauern würde, und bei 1.000.000 Wörtern sogar 200 Minuten, also über drei Stunden. Und das, wo 1.000.000 nach gar nicht so viel klingt für heutige Rechner.

Übungsaufgabe Überprüfen Sie die Aussage Für doppelt so große Arryas brauchen InsertionSort und SelectionSort viermal so lange empirisch, indem Sie Ihre Implementierung testen.