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

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

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.

InsertionSort

Ähnlich wie SelectionSort gilt auch bei InsertionSort, dass am Anfang von Phase $$ die ersten $$ Elemente des Arrays sortiert sind. Allerdings sind diese nicht notwenidgerweise die kleinsten $$ Elemente des gesamten Arrays, sondern sind identisch mit den ersten $$ 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

                

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

Laufzeitanalyse

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 $$; 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$$, gegenüberstellen, bekommen wir folgende Rechnung:

Für großes $$ konvergiert der Wert in der Klammer gegen $$. 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.