Einfache Sortierverfahren und ihre Laufzeit

Im Folgenden entwickeln wir Prozeduren, die eine Liste als Argument erwarten und als Seiteneffekt die Elemente in der gegebenen Liste sortieren. Als Elemente werden wir Zahlen verwenden, die vorgestellten Sortierverfahren sind jedoch meist auch zum Sortieren komplexerer Daten geeignet (sofern diese in einer gewissen Ordnung zueinander stehen).

Selection Sort

Ein einfaches Verfahren zum Sortieren lässt sich umgangssprachlich wie folgt beschreiben:

• Vertausche das erste mit dem kleinsten Element der Liste,
• dann das zweite mit dem kleinsten Element im Teil ohne das erste Element,
• dann das dritte mit dem kleinsten im Teil ohne die ersten beiden
• und so weiter, bis die ganze Liste durchlaufen wurde.

Dieses Verfahren heißt Selection Sort (oder Min Sort), weil die Elemente der Liste nacheinander mit dem Minimum getauscht werden, das aus der Teilliste aller folgenden Elemente ausgewählt wird. Um es in Python zu implementieren, durchlaufen wir in einer Schleife mit fester Anzahl alle Elemente der gegebenen Liste und vertauschen sie mit dem Minimum in der Rest-Liste. Die Funktion min_pos bestimmt dabei die Position des kleinsten Elements und swap vertauscht die Elemente an zwei gegebenen Indizes.

def min_sort(a):
    for i in range(0, len(a)):
        swap(a, i, min_pos(a, i))

def min_pos(a, start):
    pos = start                       #1
    for i in range(start+1, len(a)):  #2
        if a[i] < a[pos]:             #3
            pos = i                   #4
    return pos                        #5

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

Diese Funktion durchläuft die Liste ab der gegebenen Position start und merkt sich die Position pos des kleinsten bisher gefunden Elementes, die sie am Ende zurückliefert.

Die folgende Programmtabelle dokumentiert die Ausführung des Ausrufs min_pos([1,2,5,3,4],2):

Die Korrektheit dieser Funktion können wir mit Hilfe der folgenden Beobachtungen einsehen:

1. Vor dem Eintritt in die Schleife ist pos = start
2. Nach jedem Schleifendurchlauf ist pos die Position des kleinsten Elementes in a zwischen start und i.
3. Nach der Ausführung der Schleife ist pos folglich die Position des kleinsten Elements zwischen start und dem Ende der Liste.

Denken wir uns i = start in der Situation vor Eintritt in die Schleife, dann gilt die zweite Bedingung vor, während und nach der Ausführung der Schleife und heißt deshalb Schleifen-Invariante.

Auch von der Korrektheit der Prozedur min_sort können wir uns mit Hilfe einer Invariante überzeugen. Nach jedem Schleifesdurchlauf ist nämlich die Teil-Liste zwischen Position 0 und i sortiert. Insbesondere ist also der Vollendung der Schleife die gesamte Liste sortiert.

Wir können uns dies anhand eines Beispiels veranschaulichen, bei dem wir nacheinander Werte der sortierten Liste notieren, wenn dieses verändert wird. Im nächsten Schritt vertauschte Elemente sind dabei hervorgehoben. Falls nur ein Element hervorgehoben ist, wird es im nächsten Schritt mit sich selbst vertauscht.

• [1, 2, 5, 3, 4]
• [1, 2, 5, 3, 4]
• [1, 2, 5, 3, 4]
• [1, 2, 3, 5, 4]
• [1, 2, 3, 4, 5]

Die Laufzeit der Prozedur min_sort untersuchen wir experimentell, indem wir sie auf Listen unterschiedlicher Größe anwenden. Wir fangen mit einer Liste der Größe 1000 an, verdoppeln dann dreimal die Listengröße und messen die Zeit, die zum Sortieren benötigt wird:

import time, random

count = 1000
for rounds in range(0, 4):
    print(str(count) + ": ")
    nums = [None] * count
    for i in range(count):
        nums[i] = random.randrange(10000)
    start = time.process_time()
    min_sort(nums)
    print(str(time.process_time() - start))
    count = 2 * count

Dieses Programm gibt neben der Eingabegröße die zum Sortieren benötigte Zeit in Sekunden aus. Die Ausgabe variiert je nach Rechner auf dem das Programm ausgeführt wird. Auf meinem Laptop ergibt sich:

1000: 
0.027022123336791992
2000: 
0.11847710609436035
4000: 
0.4383370876312256
8000: 
1.7466981410980225

Wir können beobachten, dass sich die Laufzeit bei Verdoppelung der Eingabegröße jedesmal ungefähr vervierfacht.

Da die Prozedur min_sort nur Zählschleifen verwendet, hängt ihre Laufzeit nur unwesentlich davon ab, welche Elemente die gegebene Liste enthält. Im Falle einer bereits sortierten Liste wird der Rumpf pos = i der bedingten Anweisung in der Funktion min_pos() niemals ausgeführt, da die Bedingung a[i] < a[pos] immer False ist. Eine Zuweisung wird in der Regel jedoch neben der Vergleichsoperation vernächlässigt, die hier unabhängig von der Eingabe immer gleich häufig ausgeführt wird.