Im Folgenden entwickeln wir Prozeduren, die ein Array als Argument erwarten und als Seiteneffekt die Elemente im gegebenen Array 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).
Ein einfaches Verfahren zum Sortieren lässt sich umgangssprachlich wie folgt beschreiben:
Dieses Verfahren heißt Selection Sort (oder Min Sort), weil die Elemente des Arrays nacheinander mit dem Minimum getauscht werden, das aus dem Teilarray aller folgenden Elemente ausgewählt wird. Um es in Python zu implementieren, durchlaufen wir in einer Schleife mit fester Anzahl alle Elemente des gegebenen Arrays und vertauschen sie mit dem Minimum im Rest-Array. 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 das Array 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):
| PP | pos | i | a[i] < a[pos] | return |
|---|---|---|---|---|
| #1 | 2 | |||
| #2 | 3 | |||
| #3 | True | |||
| #4 | 3 | |||
| #2 | 4 | |||
| #3 | False | |||
| #5 | 3 |
Die Korrektheit dieser Funktion können wir mit Hilfe der folgenden Beobachtungen einsehen:
pos = startpos die Position des kleinsten Elementes in a zwischen start und i.pos folglich die Position des kleinsten Elements zwischen start und dem Ende des Arrays.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 das Teil-Array zwischen Position 0 und i sortiert. Insbesondere ist also der Vollendung der Schleife das gesamte Array sortiert.
Wir können uns dies anhand eines Beispiels veranschaulichen, bei dem wir nacheinander Werte des sortierten Arrays 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.
Die Laufzeit der Prozedur min_sort untersuchen wir experimentell, indem wir sie auf Arrays unterschiedlicher Größe anwenden. Wir fangen mit einem Array der Größe 1000 an,
verdoppeln dann dreimal die Arraygröß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.time()
min_sort(nums)
print(str(time.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 das gegebene Array enthält. Im Falle eines bereits sortierten Arrays 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.