Zur Implementierung von Max Sort durchlaufen wir das Feld von hinten nach vorne und tauschen dabei jeweils das entsprechende Element mit dem größten seiner Vorgänger. Wir definieren dazu einen Index j in Abhängigkeit von i, der das Feld rückwärts durchläuft.
def max_sort(a):
for i in range(0, len(a)):
j = len(a) - i - 1
swap(a, j, max_pos(a, j))
Ein Aufruf max_pos(a, to) liefert die Position des größten Elementes in a bis zur Position to.
def max_pos(a, to):
pos = 0
for i in range(0, to):
if a[i+1] > a[pos]:
pos = i + 1
return pos
Bei den durchgeführten Tests mit sortierten Listen ist insertion_sort deutlich schneller als min_sort:
1000:
0.00014853477478027344
2000:
0.0003032684326171875
4000:
0.0005826950073242188
8000:
0.0012249946594238281
Die wichtigere Beobachtung ist jedoch nicht, dass die Laufzeiten geringer sind, sondern, dass sie langsamer ansteigen: Bei Verdoppelung der Eingabegröße ergibt sich ungefähr die doppelte Laufzeit und nicht mehr wie bei min_sort die vierfache.
Dies gilt jedoch nur für bereits sortierte Listen. Um unsere Tests mit unsortierten Listen zu wiederholen, definieren wir eine Funktion, die umgekehrt sortierte Listen gegebener Größe erzeugt.
def descending(size):
a = [None] * size
for i in range(0, size):
a[i] = size - i
return a
Zum Beispiel liefert der Aufruf descending(5) das Ergebnis [5,4,3,2,1] zurück. Wenn wir diese Funktion zum Erzeugen der Testeingaben verwenden, ergibt sich die folgende Ausgabe:
1000:
0.12551259994506836
2000:
0.49935364723205566
4000:
2.014533519744873
8000:
8.014490604400635
Bei Verdoppelung der Eingabegröße umgekehrt sortierter Listen vervierfacht sich also die Laufzeit von Insertion Sort, wie wir es auch schon bei Selection Sort beobachtet hatten.
Die folgende rekursive Prozedur implementiert den Insertion Sort Algorithmus.
def ins_sort(a, to):
if to > 0:
ins_sort(a, to-1)
insert_backwards(a, to)
Falls to <= 0 gilt, ist das zu sortierende Anfangsstück bereits
sortiert, da es aus höchstens einem Element besteht. Falls to > 0
ist, sortieren wir rekursiv das Anfangsstück bis zur Position to-1
und fügen dann das Element an Position to rückwärts in den
sortierten Bereich ein.
Die rekursive Implementierung führt die selben Vergleiche und Vertauschungen aus wie die vorherige Implementierung mit einer Zählschleife. Die Laufzeiten der beiden Implementierungen sind also ungefähr gleich.
Zu Beginn wird die Liste
a = [3,2,1,6,7,4,8,5]
mit dem Aufruf partition(a,0,7) partitioniert. Nach diesem Aufruf (der die Position 2 zurückliefert) sind die Elemente von a wie folgt umgeordnet.
a = [1,2,3,6,7,4,8,5]
Nun wird der Bereich von Position 0 bis 1 mit dem Aufruf partition(a,0,1) partitioniert, wobei keine Elemente vertauscht werden. Anschließend folgt der Aufruf partition(a,3,7) des zweiten rekursiven Aufrufs von quick_sort. Er liefert als Ergebnis die Position 5 zurück und ordnet die Elemente in a wie folgt um.
a = [1,2,3,5,4,6,8,7]
Schließlich folgen in weiteren rekursiven Aufrufen von quick_sort die Aufrufe partition(a,3,4) und partition(a,6,7), die nacheinandner dafür sorgen, dass a sortiert wird.
a = [1,2,3,4,5,6,8,7]
a = [1,2,3,4,5,6,7,8]
Der Rumpf der mutierenden Prozedur simple_sort enthält
zwei geschachtelte Zählschleifen.
Die äußere verwendet die Zählvariable i, die innere j.
Der innere Schleifenrumpf enthält eine optionale Anweisung
deren Bedingung die Elemente an den Indizes i und j vergleicht.
Im Rumpf der optionalen Anweisung steht ein Aufruf der Prozedur swap.
Die folgende Programmtabelle dokumentiert die Ausführung des Aufrufs simple_sort([2,1,3]).
| PP | i | j | a[i] < a[j] | a |
|---|---|---|---|---|
| 0 | [2,1,3] | |||
| 1 | 0 | |||
| 2 | 0 | |||
| 3 | False | |||
| 2 | 1 | |||
| 3 | False | |||
| 2 | 2 | |||
| 3 | True | |||
| 4 | [3,1,2] | |||
| 1 | 1 | |||
| 2 | 0 | |||
| 3 | True | |||
| 4 | [1,3,2] | |||
| 2 | 1 | |||
| 3 | False | |||
| 2 | 2 | |||
| 3 | False | |||
| 1 | 2 | |||
| 2 | 0 | |||
| 3 | False | |||
| 2 | 1 | |||
| 3 | True | |||
| 4 | [1,2,3] | |||
| 2 | 2 | |||
| 3 | False |
Die Prozedur simple_sort sortiert jede beliebige übergebene Liste von Zahlen.
Relevant für die Laufzeit ist vor allem die Anzahl durchgeführter Vergleiche. Sie ist eine obere Schranke für die Anzahl der durchgeführten Vertauschungen. Die Laufzeit ist beschrieben durch $O(n^2)$, falls $n$ die Anzahl der Elemente der übergebenen Liste ist.
Alle in der Aufgabe genannten Aussagen treffen zu.
Die rekursive Funktion merge_sort liefert eine Kopie ihrer Eingabe zurück, wenn diese höchstens ein Element enthält. Wenn nicht, wird die übergebene Liste in zwei Hälften geteilt, die rekursiv sortiert und dann zusammengeführt werden.
def merge_sort(a):
if len(a) <= 1:
return a + [] # return a copy
else:
half = len(a) // 2
return merge(merge_sort(a[0:half]), merge_sort(a[half:len(a)]))
Die Funktion merge fügt zwei sortierte Listen zu einer sortierten Liste zusammen:
def merge(a, b):
c = [None] * (len(a) + len(b))
l = 0
r = 0
# as long as there are elements left
while l + r < len(c):
# we pick the next element from a
if l < len(a) and (r >= len(b) or a[l] <= b[r]):
c[l+r] = a[l]
l = l + 1
else: # or the next element from b
c[l+r] = b[r]
r = r + 1
return c
Sowohl für sortierte als auch für unsortierte Eingaben wird die Laufzeit bei Verdoppelung der Eingabegröße etwas mehr als verdoppelt. Dies legt die (tatsächlich zutreffende) Vermutung nah, dass die Laufzeit in \(O(n\cdot log(n))\) ist.
def swap(a, i, j):
temp = a[i]
a[i] = a[j]
a[j] = temp
def left_child(pos):
return 2*pos + 1
def right_child(pos):
return 2*pos + 2
# restore heap property (node >= child) assuming it for children
def repair(a, root, size):
max = root
left = left_child(root)
if left < size and a[max] < a[left]: # left child exists and is larger
max = left
right = right_child(root)
if right < size and a[max] < a[right]: # right child exists and is larger
max = right
if max != root: # heap property is violated
swap(a, root, max)
repair(a, max, size)
def make_heap(a):
for i in range(0, len(a)):
repair(a, len(a) - i - 1, len(a))
def heap_sort(a):
make_heap(a)
for i in range(0, len(a)-1):
j = len(a) - i - 1
swap(a, 0, j)
repair(a, 0, j)