2.8. Sortieralgorithmus#
Mittels Schleifen und Abzweigungen wird eine Funktion zum Sortieren von Zahlenlisten implementiert.
Aufgabenteil A#
Implementieren Sie die den Bubblesort Algorithmus als eine eigene Funktion. Sie bekommt als Argument eine Liste, welche nach der Größe ihrer Elemente sortiert werden soll, und das Ergebnis zurückgibt. Als optionaler Parameter soll eine Ausgabe gesteuert werden, welche den Zwischenzustand der zu sortierenden Liste ausgibt.
Testen Sie ihre Funktion anhand folgender Zufallszahlen:
9, 74, 90, 23, 69, 10, 72, 93, 99, 91, 45, 81, 4, 71, 14, 16, 50, 53, 82, 47, 40, 44, 4, 30, 32, 73, 99, 93, 65, 36
69, 70, 93, 25, 85, 68, 73, 97, 22, 35, 41, 99, 22, 33, 56, 95, 86, 45, 24, 64, 73, 60, 53, 40, 94, 12, 97, 18, 75, 8
84, 51, 4, 8, 28, 55, 64, 25, 1, 47, 8, 66, 12, 60, 28, 18, 89, 37, 2, 48, 92, 74, 78, 28, 35, 87, 88, 51, 57, 6
Lösungshinweis#
Um zu prüfen ob Ihre Funktion richtig arbeitet, können Sie eine weitere Funktion schreiben, welche prüft, ob eine Liste sortiert ist.
t1 = [9, 74, 90, 23, 69, 10, 72, 93, 99, 91,
45, 81, 4, 71, 14, 16, 50, 53, 82, 47,
40, 44, 4, 30, 32, 73, 99, 93, 65, 36]
t2 = [69, 70, 93, 25, 85, 68, 73, 97, 22, 35,
41, 99, 22, 33, 56, 95, 86, 45, 24, 64,
73, 60, 53, 40, 94, 12, 97, 18, 75, 8]
t3 = [84, 51, 4, 8, 28, 55, 64, 25, 1, 47,
8, 66, 12, 60, 28, 18, 89, 37, 2, 48,
92, 74, 78, 28, 35, 87, 88, 51, 57, 6]
Lösungsvorschlag#
Um lange Listen in dem Skript kompakt darstellen zu können, wird im Folgenden diese Funktion verwendet:
Show code cell content
# Hilfsfunktion zur Ausgabe langer Listen im Skript
def list_str(A, n=10):
res = ""
res += "["
nflines = len(A)//n
nhlines = len(A)%n
for i in range(nflines):
if nflines > 0:
res += " "
for j in range(n):
res += str(A[i*n+j])
if i*n+j < len(A)-1:
res += ", "
if not (nhlines == 0 and i == nflines-1):
res += "\n"
for j in range(nhlines):
res += str(A[nflines*n+j])
if j < nhlines-1:
res += ", "
res += "]"
return res
Show code cell content
def bubble_sort(A, ausgabe=False):
# Initialer Wert für n, wird bei jedem Schleifendurchlauf
# um Eins verringert
n = len(A)
# Variable zum Prüfen ob eine Vertauschung erfolgt ist
# initial wird sie auf wahr gesetzt
getauscht = True
# Iterationszähler
izaehler = 0
while getauscht == True:
getauscht = False
izaehler += 1
if ausgabe == True:
print("Iteration:", izaehler)
print(" Liste zu Beginn der Iteration: ")
print(" ", list_str(A))
# Vertauschungsschleife
for j in range(n-1):
# Prüfen ob das nachfolgende Element kleiner ist,
# falls ja, werden beide getauscht
if A[j+1] < A[j]:
if ausgabe == True:
print(" Tausche: ", A[j], "und", A[j+1])
# Tauschen des j mit dem j+1 Elementwert
mv = A[j]
A[j] = A[j+1]
A[j+1] = mv
# Markierung, dass eine Vertauschung stattfand
getauscht = True
if ausgabe == True:
print(" Liste nach Tausch: ")
print(" ", list_str(A))
else:
if ausgabe == True:
print(" Elemente ", A[j], "und", A[j+1], " müssen nicht getauscht werden")
# Schleifendurchlauf wird verkürzt
n -= 1
if not getauscht:
if ausgabe == True:
print(" kein Tausch mehr notwendig, Liste ist nun sortiert")
return A
Show code cell content
print( list_str(t1) )
print( list_str( bubble_sort(t1) ) )
[ 9, 74, 90, 23, 69, 10, 72, 93, 99, 91,
45, 81, 4, 71, 14, 16, 50, 53, 82, 47,
40, 44, 4, 30, 32, 73, 99, 93, 65, 36]
[ 4, 4, 9, 10, 14, 16, 23, 30, 32, 36,
40, 44, 45, 47, 50, 53, 65, 69, 71, 72,
73, 74, 81, 82, 90, 91, 93, 93, 99, 99]
Show code cell content
# Funktion zum Prüfen der Sortierung
def pruefe_sortierung(A):
for i in range(len(A)-1):
if A[i+1] < A[i]:
return False
return True
Show code cell content
print( list_str( t2 ) )
t2_sort = bubble_sort(t2)
print( list_str( t2_sort) )
print("Sortiert?", pruefe_sortierung(t2_sort))
[ 69, 70, 93, 25, 85, 68, 73, 97, 22, 35,
41, 99, 22, 33, 56, 95, 86, 45, 24, 64,
73, 60, 53, 40, 94, 12, 97, 18, 75, 8]
[ 8, 12, 18, 22, 22, 24, 25, 33, 35, 40,
41, 45, 53, 56, 60, 64, 68, 69, 70, 73,
73, 75, 85, 86, 93, 94, 95, 97, 97, 99]
Sortiert? True
Show code cell content
t2_sort[3] = 50
print( list_str(t2_sort) )
print("Sortiert?", pruefe_sortierung(t2_sort))
[ 8, 12, 18, 50, 22, 24, 25, 33, 35, 40,
41, 45, 53, 56, 60, 64, 68, 69, 70, 73,
73, 75, 85, 86, 93, 94, 95, 97, 97, 99]
Sortiert? False
Show code cell content
t3 = [84, 51, 4, 8, 28, 55, 64, 25, 1, 47,
8, 66, 12, 60, 28, 18, 89, 37, 2, 48,
92, 74, 78, 28, 35, 87, 88, 51, 57, 6]
t3_sort = bubble_sort(t3[:10], ausgabe=True)
Iteration: 1
Liste zu Beginn der Iteration:
[ 84, 51, 4, 8, 28, 55, 64, 25, 1, 47]
Tausche: 84 und 51
Liste nach Tausch:
[ 51, 84, 4, 8, 28, 55, 64, 25, 1, 47]
Tausche: 84 und 4
Liste nach Tausch:
[ 51, 4, 84, 8, 28, 55, 64, 25, 1, 47]
Tausche: 84 und 8
Liste nach Tausch:
[ 51, 4, 8, 84, 28, 55, 64, 25, 1, 47]
Tausche: 84 und 28
Liste nach Tausch:
[ 51, 4, 8, 28, 84, 55, 64, 25, 1, 47]
Tausche: 84 und 55
Liste nach Tausch:
[ 51, 4, 8, 28, 55, 84, 64, 25, 1, 47]
Tausche: 84 und 64
Liste nach Tausch:
[ 51, 4, 8, 28, 55, 64, 84, 25, 1, 47]
Tausche: 84 und 25
Liste nach Tausch:
[ 51, 4, 8, 28, 55, 64, 25, 84, 1, 47]
Tausche: 84 und 1
Liste nach Tausch:
[ 51, 4, 8, 28, 55, 64, 25, 1, 84, 47]
Tausche: 84 und 47
Liste nach Tausch:
[ 51, 4, 8, 28, 55, 64, 25, 1, 47, 84]
Iteration: 2
Liste zu Beginn der Iteration:
[ 51, 4, 8, 28, 55, 64, 25, 1, 47, 84]
Tausche: 51 und 4
Liste nach Tausch:
[ 4, 51, 8, 28, 55, 64, 25, 1, 47, 84]
Tausche: 51 und 8
Liste nach Tausch:
[ 4, 8, 51, 28, 55, 64, 25, 1, 47, 84]
Tausche: 51 und 28
Liste nach Tausch:
[ 4, 8, 28, 51, 55, 64, 25, 1, 47, 84]
Elemente 51 und 55 müssen nicht getauscht werden
Elemente 55 und 64 müssen nicht getauscht werden
Tausche: 64 und 25
Liste nach Tausch:
[ 4, 8, 28, 51, 55, 25, 64, 1, 47, 84]
Tausche: 64 und 1
Liste nach Tausch:
[ 4, 8, 28, 51, 55, 25, 1, 64, 47, 84]
Tausche: 64 und 47
Liste nach Tausch:
[ 4, 8, 28, 51, 55, 25, 1, 47, 64, 84]
Iteration: 3
Liste zu Beginn der Iteration:
[ 4, 8, 28, 51, 55, 25, 1, 47, 64, 84]
Elemente 4 und 8 müssen nicht getauscht werden
Elemente 8 und 28 müssen nicht getauscht werden
Elemente 28 und 51 müssen nicht getauscht werden
Elemente 51 und 55 müssen nicht getauscht werden
Tausche: 55 und 25
Liste nach Tausch:
[ 4, 8, 28, 51, 25, 55, 1, 47, 64, 84]
Tausche: 55 und 1
Liste nach Tausch:
[ 4, 8, 28, 51, 25, 1, 55, 47, 64, 84]
Tausche: 55 und 47
Liste nach Tausch:
[ 4, 8, 28, 51, 25, 1, 47, 55, 64, 84]
Iteration: 4
Liste zu Beginn der Iteration:
[ 4, 8, 28, 51, 25, 1, 47, 55, 64, 84]
Elemente 4 und 8 müssen nicht getauscht werden
Elemente 8 und 28 müssen nicht getauscht werden
Elemente 28 und 51 müssen nicht getauscht werden
Tausche: 51 und 25
Liste nach Tausch:
[ 4, 8, 28, 25, 51, 1, 47, 55, 64, 84]
Tausche: 51 und 1
Liste nach Tausch:
[ 4, 8, 28, 25, 1, 51, 47, 55, 64, 84]
Tausche: 51 und 47
Liste nach Tausch:
[ 4, 8, 28, 25, 1, 47, 51, 55, 64, 84]
Iteration: 5
Liste zu Beginn der Iteration:
[ 4, 8, 28, 25, 1, 47, 51, 55, 64, 84]
Elemente 4 und 8 müssen nicht getauscht werden
Elemente 8 und 28 müssen nicht getauscht werden
Tausche: 28 und 25
Liste nach Tausch:
[ 4, 8, 25, 28, 1, 47, 51, 55, 64, 84]
Tausche: 28 und 1
Liste nach Tausch:
[ 4, 8, 25, 1, 28, 47, 51, 55, 64, 84]
Elemente 28 und 47 müssen nicht getauscht werden
Iteration: 6
Liste zu Beginn der Iteration:
[ 4, 8, 25, 1, 28, 47, 51, 55, 64, 84]
Elemente 4 und 8 müssen nicht getauscht werden
Elemente 8 und 25 müssen nicht getauscht werden
Tausche: 25 und 1
Liste nach Tausch:
[ 4, 8, 1, 25, 28, 47, 51, 55, 64, 84]
Elemente 25 und 28 müssen nicht getauscht werden
Iteration: 7
Liste zu Beginn der Iteration:
[ 4, 8, 1, 25, 28, 47, 51, 55, 64, 84]
Elemente 4 und 8 müssen nicht getauscht werden
Tausche: 8 und 1
Liste nach Tausch:
[ 4, 1, 8, 25, 28, 47, 51, 55, 64, 84]
Elemente 8 und 25 müssen nicht getauscht werden
Iteration: 8
Liste zu Beginn der Iteration:
[ 4, 1, 8, 25, 28, 47, 51, 55, 64, 84]
Tausche: 4 und 1
Liste nach Tausch:
[ 1, 4, 8, 25, 28, 47, 51, 55, 64, 84]
Elemente 4 und 8 müssen nicht getauscht werden
Iteration: 9
Liste zu Beginn der Iteration:
[ 1, 4, 8, 25, 28, 47, 51, 55, 64, 84]
Elemente 1 und 4 müssen nicht getauscht werden
kein Tausch mehr notwendig, Liste ist nun sortiert
Aufgabenteil B#
Erweitern Sie die obige Funktion um eine weitere Rückgabe. Diese soll die Anzahl der durchgeführten Vertauschungen enthalten. Untersuchen Sie wie diese Anzahl mit der Länge der zu sortierenden Liste zusammenhängt. Sie können sich auf die obigen Datensätze beschränken.
Lösungsvorschlag#
Show code cell content
def bubble_sort_zaehler(A):
# Initialer Wert für n, wird bei jedem Schleifendurchlauf
# um Eins verringert
n = len(A)
# Variable zum Prüfen ob eine Vertauschung erfolgt ist
# initial wird sie auf wahr gesetzt
getauscht = True
# Zähler für Vertauschungen
vertauschungen = 0
# Schleife wird solgange ausgeführt bis keine
# weitere Vertauschung notwendig ist
while getauscht == True:
getauscht = False
# Vertauschungsschleife
for j in range(n-1):
# Prüfen ob das nachfolgende Element kleiner ist,
# falls ja, werden beide getauscht
if A[j+1] < A[j]:
# Tauschen des j mit dem j+1 Elementwert
mv = A[j]
A[j] = A[j+1]
A[j+1] = mv
# Markierung, dass eine Vertauschung stattfand
getauscht = True
# Erhöhe Zähler der Vertauschungen
vertauschungen += 1
# Schleifendurchlauf wird verkürzt
n -= 1
# Rückgabe der sortierten Liste als auch der Anzahl
# der Vertauschungen
return A, vertauschungen
Show code cell content
t2 = [69, 70, 93, 25, 85, 68, 73, 97, 22, 35,
41, 99, 22, 33, 56, 95, 86, 45, 24, 64,
73, 60, 53, 40, 94, 12, 97, 18, 75, 8]
print( list_str( t2 ) )
t2_sort, v = bubble_sort_zaehler(t2)
print( list_str( t2_sort ) )
print( "Anzahl der Vertauschungen:", v)
[ 69, 70, 93, 25, 85, 68, 73, 97, 22, 35,
41, 99, 22, 33, 56, 95, 86, 45, 24, 64,
73, 60, 53, 40, 94, 12, 97, 18, 75, 8]
[ 8, 12, 18, 22, 22, 24, 25, 33, 35, 40,
41, 45, 53, 56, 60, 64, 68, 69, 70, 73,
73, 75, 85, 86, 93, 94, 95, 97, 97, 99]
Anzahl der Vertauschungen: 245
Show code cell content
print("N\tAnzahl Vertauschungen")
print("="*29)
for N in range(30):
t2 = [69, 70, 93, 25, 85, 68, 73, 97, 22, 35,
41, 99, 22, 33, 56, 95, 86, 45, 24, 64,
73, 60, 53, 40, 94, 12, 97, 18, 75, 8]
t2_sort, v = bubble_sort_zaehler(t2[:N])
print(N, '\t', v)
N Anzahl Vertauschungen
=============================
0 0
1 0
2 0
3 0
4 3
5 4
6 8
7 10
8 10
9 18
10 25
11 32
12 32
13 43
14 53
15 61
16 63
17 67
18 78
19 94
20 104
21 110
22 122
23 136
24 153
25 156
26 181
27 182
28 208
29 216