2. Suchen und Sortieren

2.2 Naive Sortieralgorithmen

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 Python schaut das so aus:

def selectionSort(array):
array = array[0:] # wir fertigen hier eine Kopie an, um das ursprüngliche Array unangetastet zu lassen
    n = len(array) 
    for k in range(n):
        argmin = findArgmin(array, k, n-1) 
        swap (array, argmin, k)
    return array

Die Funktion argmin(array, a, b) sucht den Index des kleinsten Elements in array[a], array[a+1], ..., array[b]. Die Funktion swap vertauscht die Elemente an den beiden Indizes. Hier ist der Code:

def swap(array, i, j):
    temp = array[i]
    array[i] = array[j]
    array[j] = temp

def findArgmin (array, lower, upper):
    i = lower 
    argmin = lower 
    for i in range(lower, upper+1):
        if array[i] < array[argmin]:
            argmin = i 
    return argmin 

~/AuK/code/sorting $ python3 -i selectionSort.py
wordlist_unsorted[:10]
['joblessness', 'presets', 'yeaned', 'birefringence', 'splutter', 'destabilisation', 'brags', 'supplies', 'enthroned', 'crests']

selectionSort(wordlist_unsorted[:10])

measure_alg(selectionSort, wordlist_unsorted[0:1000])

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

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.

Laufzeitanalyse

Sowohl SelectionSort als auch InsertionSort machen also ungefähr \(n^2\) Vergleichsoperationen, und ihre Laufzeit ist daher auch ungefähr \(n^2\). In dieser Vorlesung werden Sie auch lernen, wie man auf mathematisch rigorose Weise über solche unpräzisen Größen sprechen kann. Der Sinn dahinter ist: ob ein Algorithmus \(\frac{n^2}{2} - \frac{n}{2}\) oder \(\frac{n^2}{2}\) Vergleichsoperationen ausführt, ist nicht so relevant; es gibt eh andere Dinge, Implementierungsdetails, Memory-Operationen etc., die den Unterschied zwischen den beiden übertönen. Und auch ob es \(\frac{n^2}{2}\) oder \(n^2\) sind, ist oft nicht weltbewegend; schließlich können Sie den Unterschied eliminieren, indem Sie einen doppelt so schnellen Rechner kaufen (oder zwei, falls das Problem sich parallelisieren lässt). Der Unterschied zwischen einer Laufzeit, die ungefähr \(n^2\) ist und einer, die ungefähr \(n^3\) ist, wird sich nicht mit dem Kauf besserer Hardware oder einer besseren Implementierung übertünchen lassen. Sie werden in diesem Kurs also auch lernen, worauf man bei der Laufzeitanalyse von Algorithmen achten sollte.

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:

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.

random.shuffle(array)
insertionSort(array)