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:

Hide 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
Hide 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
Hide 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]
Hide 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
Hide 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
Hide 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
Hide 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#

Hide 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
Hide 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
Hide 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