Algorithmen II: Suchen & Sortieren

Suchen:

• Verschiedene Suchalgorithmen erklären …
• … und miteinander vergleichen.
• Performance von Suchalgorithmus analysieren (Anzahl Suchschritte im Best- und Worst-Case).

PLZ-Datensatz}} beinhaltet drei lange Listen mit sämtlichen Postleitzahlen, den zugehörigen Ortschaften und Kantonen.

• Diese Aufgaben löst man ohne die lineare_search-Funktion.
• Du kannst die Aufgabe lösen, indem du eine neue Funktion programmierst (die natürlich viele Ähnlichkeiten mit der lineare_search-Funktion hat). Du kannst aber auch einfach eine Schleife programmieren, die nicht in einer Funktion steht.
• Idee: Gehe alle Positionen der Postleitzahlen durch und schaue, zu welchem Kanton sie gehören. Falls sie zum richtigen gehören, erhöhe einen Counter um 1.

Das Problem ist, dass man versuchen muss, Duplikate zu verhindern. Dazu kann man alle Ortsnamen des Kantons Zürichs in eine Liste schreiben. Fügt man einen neuen hinzu, überprüft man, ob der Name bereits in der Liste vorkommt. Nur wenn nicht fügt man diesen hinzu.

Code zum Überprüfen, ob ein Element el (nicht) bereits in einer Liste li vorkommt:

if el in li:
    # Code der ausgefuehrt wird, wenn el bereits in li vorkommt
 
if not el in li:
    # Code der ausgefuehrt wird, wenn el NICHT bereits in li vorkommt

1. Laufen Basel-Landschaft
2. Weinfelden Thurgau
3. 4704 Bern
4. 27
5. 199
6. 263
7. 70927

• Wir merken uns zwei Variablen, left und right, die die Position des Suchbereichs abstecken: left ist die Position des kleinsten Elements, right die Position des grössten Elements, das noch in Frage kommt. Zu Beginn ist left natürlich null, und right ist der Index des letzten Elements (also len(l) - 1).
• In der while-Schleife manipulieren wir nun diese Positionen, indem wir eine Position in der Mitte der beiden auswählen: middle = .... Das Element in der Mitte (l[middle]) können wir nun mit dem gesuchten Element vergleichen. Was tun wir, wenn das Mitte-Element genau der Suche entspricht? Wenn das gesuchte Element kleiner oder grösser als das in der Mitte ist, müssen left oder right angepasst werden - aber wie genau?
• Um eine Ganzzahl-Division (ohne Rest) durchzuführen, benützen wir in Python den // Operator.

Es gibt viele verschiedene Sortieralgorithmen. Zuerst schauen wir uns den sogenannten Selectionsort-Algorithmus: Das Ziel von diesem ist, zuerst das kleinste Element in der Liste zu finden und diese an der ersten Stelle zu platzieren. Danach machen wir weiter mit dem zweitkleinsten Element usw. Doch wie finden wir im ersten Durchlauf das kleinste Element? Wir vergleichen das erste Element (Index 0) der Reihe nach mit allen anderen Elementen der Liste. Ist ein anderes Element kleiner, so vertauschen wir die beiden.

Simuliere diesen Algorithmus mithilfe der Kärtchen:

1. Lege die Kärtchen in zufälliger Reihenfolge vor dir auf den Tisch.
2. Positioniere deinen linken Zeigefinger beim ersten Kärtchen.
3. Positioniere deinen rechten Zeigefinger beim Kärtchen rechts daneben.
4. Ist das rechte Kärtchen kleiner? Falls ja, vertausche die beiden.
5. Gehe nun mit dem rechten Finger alle Kärtchen durch bis du ganz rechts angelangst. Vertausche immer falls nötig die Kärtchen. Der linke Finger bewegt sich nicht und zeigt immer zum ersten Kärtchen.
6. Nach diesem ersten Durchlauf weisst du, dass das Kärtchen ganz links das kleinste ist.
7. Bewege deinen linken Finger nun um eins nach rechts.
8. Wiederhole die Schritte ab 3. solange, bis du mit dem linken Finger rechts angekommen bist.
9. Jetzt sollten die Kärtchen korrekt sortiert sein.

• Elemente einer Liste vertauschen: Ziel, das 3. und 7. Element einer Liste li vertauschen:

temp = li[3]  # speichere altes Element an Position 3 in temporaerer Variable
li[3] = li[7] # ueberschreibe das Element an Pos. 3 mit demjenigen an Pos. 7
li[7] = temp  # schreibe Wert in temp (alter Wert an Pos 3) in Pos. 7

• Man benötigt zwei Schleifen (ineinander verschachtelte) :
  • Eine, die den linken Zeigefinger simuliert, also einmal von links nach rechts läuft …
  • und eine, die den rechten Zeigefinger simuliert, also immer rechts vom linken Zeigefinger startet und bis ganz nach rechts läuft.

Beim Bubblesort geht man die ganze Liste von links nach rechts durch. Man vergleicht immer zwei benachbarte Kärtchen und vertausche sie, falls das rechte Kärtchen kleiner ist. Nach dem ersten Durchgang ist die Liste besser (aber meist nicht komplett) sortiert als am Anfang. Man wiederholt nun diesen Schritt solange, bis die Liste sortiert ist.

Frage: Wie weiss man, wann man aufhören kann?

1. Programmiere zuerst den ersten Durchlauf: Die Liste soll einmal durchgegangen werden. Dabei sollen immer zwei aufeinanderfolgenden Elemente verglichen werden. Ist dasjenige rechts kleiner, soll es mit dem linken vertauscht werden. Startet man mit der Liste [15, 11, 13, 10, 14], so soll diese nach diesem ersten Durchlauf wie folgt aussehen: [11, 13, 10, 14, 15]
2. Wiederhole nun den 1. Schritt mehrfach, bis die Liste sortiert wurde.
3. Wahrscheinlich hast du im 2. Schritt eine while- oder for-Schleife verwendet, die den Code aus 1. eine fixe Anzahl mal durchlaufen lässt. Dies ist ineffizient, da der Code weiterläuft, selbst wenn die Liste bereits sortiert wurde. Zum Beispiel reichen für die Liste [10,13,12,11,14,15] zwei Durchgänge. Überlege dir, wie du den Sortiervorgang abbrechen kannst, sobald die Liste sortiert ist.
4. Man kann den Bubble Sort auch mit nur einer einzigen while-Schleife programmieren, das ist aber eher etw. anspruchsvoller.

1. Beginne mit dem zweiten Element und vergleiche es mit dem ersten. Falls das zweite Kleiner ist, füge es an der Position des ersten Elementes ein (einfügen = insert). Nun sind die ersten beiden Elemente sortiert.
2. Betrachte nun das dritte Element und füge es in der bereits sortierten Teilliste am korrekten Platz ein.
3. Gehe weiter zum vierten Element usw.

• Verwende break um eine Schleife abzubrechen

Aufgabe A2

• Algorithmus ist sehr ineffizient. Wird Wort gesucht, welches sich am Ende befindet, dauert sehr lange.
• Suchwaufwand skaliert linear: Ist das Buch doppelt so lang, wird die (durchschnittliche) Suche auch doppelt so lange dauern. Wir sprechen deshalb von linearer Suche - der Aufwand steigt linear zusammen mit der Menge der Begriffe.

Aufgabe A3

names = ['Amos', 'Daniel', 'Ezechiel', 'Habakuk', 'Haggai', 'Hosea', 'Jeremia', 'Jesaja', 'Joel', 'Jona', 'Maleachi', 'Micha', 'Nahum', 'Obadja', 'Sacharja', 'Zefanja']
numbers = ['0790000000', '0791111111', '0792222222', '0793333333', '0794444444', '0795555555', '0796666666', '0797777777', '0798888888', '0799999999', '0791234567', '0793213213', '0794565656', '0797898989', '0799876543', '0798767676']
 
def linear_search(li,el):
    i = 0
    while i < len(li):
        if el == li[i]:
            return i
        i = i + 1
    return None
 
print(linear_search(names,'Haggai'))
 
i_micha = linear_search(names,'Micha')
print(numbers[i_micha])

Aufgabe A4

Lösungen:

1. ('Laufen', 'Basel-Landschaft')
2. ('Weinfelden', 'Thurgau')
3. (4704, 'Bern')
4. 27
5. 199
6. 263
7. 70927

Code dazu:

plzs = ...
towns = ...
towns = ...
 
# FUNCTIONS
def linear_search(L,x):
    for i in range(len(L)):
        if L[i] == x:
            return i
    return -1
 
def linear_search_count_element(L,x):
    count = 0
    for i in range(len(L)):
        if L[i] == x:
            count = count + 1
    return count
 
def quersumme(x):
    qs = 0
    x = str(x)
    for c in x:
        qs = qs + int(c)
    return qs
 
# 1. Wie heisst die Ortschaft mit der ultra-nerdigen Postleitzahl 4242 und in welchem Kanton liegt sie?
k = linear_search(plzs,4242)
print(towns[k], cantons[k])
 
# 2. Überprüfe deinen Code, in dem du die PLZ deines Wohnortes eingibst.
k = linear_search(plzs,8570)
print(towns[k], cantons[k])
 
# 3. Welche Postleitzahl hat die Ortschaft Niederbipp?
k = linear_search(towns, "Niederbipp")
print(plzs[k], cantons[k])
 
# 4. Wie viele Postleitzahlen gibt für die Stadt Zürich?
n = linear_search_count_element(towns, "Zürich")
print(n)
 
# 5. Wie viele Postleitzahlen gibt für den Kanton Thurgau?
n = linear_search_count_element(cantons, "Thurgau")
print(n)
 
# 6. Anzahl Ortsnamen im Kanton Zürich
towns_zh = []
i = 0
while i < len(cantons):
    if cantons[i] == "Zürich":
        town = towns[i]
        if not town in towns_zh:
            towns_zh.append(town)
    i = i + 1
print(len(towns_zh))
 
# 7. Sinnbefreite Zusatzaufgabe: Bestimme die Summe aller Quersummen von allen vierstelligen Zahlen, welche als Postleitzahl in der Schweiz vergeben sind.
qs = 0
for p in plzs:
    qs = qs + quersumme(p)
print(qs)

Aufgabe A5

def linear_search(li,el,is_sorted=False):
    i = 0
    while i < len(li):
        print(i)
        if li[i] == el:
            return i
        elif li[i] > el and is_sorted:
            return None
        i = i + 1
    return None

Aufgabe B1

• In einem Band mit 1000 Seiten solltest du nach 10 Teilungen auf der richtigen Seite sein.
• Zwei: Man merkt sich jeweils die obere und untere Grenze des Suchbereichs, während man in der Mitte aufschlägt.

Aufgabe B2

1. 8 Seiten: max. 4x blättern
2. 16 Seiten: max. 5x, 32: 6x, 256: 9x
3. Buch mit $2^n$ Seiten $\rightarrow$ maximal $(n+1)\times$ blättern
4. Bücher mit $513-1024$ Seiten: max 11x, da $2^{10} = 1024$
5. $2^{33} = 8589934592$, also $34\times$ blättern

Du hast Exponentialrechnung und Logarithmus eventuell noch gar nicht in der Mathematik behandelt - aber du kannst dir vorstellen, dass die Indexgrösse sehr viel stärker wächst als die Anzahl Halbierungen. Die binäre Suche ist also ein äusserst leistungsfähiger Algorithmus, um in einer sortierten Liste ein gewünschtes Element zu finden.

Allerdings funktioniert die Binärsuche nur, wenn die Sortierung unserem Such-Schlüssel entspricht. Den Namen zu einer gewünschten Telefonnummer zu finden, ist beispielsweise im klassischen Telefonbuch nicht möglich: die Nummern sind in keiner bestimmten Reihenfolge, wir müssten das ganze Telefonbuch linear durchsuchen, um die gewünschte Nummer zu finden. tel.search.ch verwendet dazu einen zweiten, invertierten Index, bei dem die Namen nach Telefonnnummer sortiert abgespeichert werden.

Aufgabe B3

def binary_search(li,el):
    left = 0
    right = len(li) - 1
    while left <= right:
        middle = left + (right - left) // 2 # alternativ: middle = (left + right) // 2
        if li[middle] == el:
            return middle
        elif el < li[middle]:
            right = middle - 1
        else:
            left = middle + 1
    return None

Aufgabe B4

• PLZ-Finder: plz: 1234, town: Vessy, canton: Genf
• PLZ-Finder: plz: 9100, town: Herisau, canton: Appenzell Ausserrhoden

Aufgabe B5

Die Liste muss sortiert sein, damit wir Binärsuche verwenden können. Das Dataset ist aber nach PLZ sortiert, nicht nach Ortsnamen. Wir müssten ein Kopie anfertigen und alle drei Listen nach Ortsnamen sortieren.

Aufgabe B6

def binary_search(li,el,left=None,right=None):
    if left == None and right == None: # set left and right at beginning of recursion
        left = 0
        right = len(li) - 1
 
    if left == right: # end of search
        if li[left] == el:
            return left
        else:
            return None
 
    mid = (left + right) // 2
    if el == li[mid]:
        return mid
    elif el < li[mid]:
        right = mid - 1
    else:
        left = mid + 1
    return binary_search(li,el,left,right)

Aufgabe 2: Selection Sort

def selection_sort(li):
    left = 0
    while left < len(li) - 1: # geht nur bis zweitletztem Element
        right = left + 1 # geht von rechts von left ...
        while right < len(li): # ... bis zum Ende der Liste
            if li[right] < li[left]: # vertausche falls El rechts kleiner
                temp = li[right]
                li[right] = li[left]
                li[left] = temp
            right = right + 1
        left = left + 1
    return li

Zusatzaufgabe: Zufallsliste erzeugen

import random
 
def random_list(n):
    i = 0
    li = []
    while i < n:
        li.append(random.choice("ABCDEFGHIJKLMNOPQRSTUVWXYZ"))
        i = i + 1
    return li
 
print(random_list(10))

Aufgabe 3

def bubble_sort_1(li):
    while True:
        count_swap = 0 # muss nach jedem Durchlauf zurueckgesetzt werden
        i = 0
        while i < len(li) - 1:
            if li[i+1] < li[i]:
                li[i],li[i+1] = li[i+1],li[i]
                count_swap = count_swap + 1
            i = i + 1
        if count_swap == 0:
            return li
 
def bubble_sort_1b(li): # wie oben, aber mit for (fuer innere Schleife)
    while True:
        count_swap = 0 # muss nach jedem Durchlauf zurueckgesetzt werden
        for i in range(len(li)-1):
            if li[i+1] < li[i]:
                li[i],li[i+1] = li[i+1],li[i]
                count_swap = count_swap + 1
        if count_swap == 0:
            return li
 
def bubble_sort_2(li):
    is_ordered = False
    while not is_ordered:
        is_ordered = True
        i = 0
        while i < len(li) - 1:
            if li[i+1] < li[i]:
                li[i],li[i+1] = li[i+1],li[i]
                is_ordered = False
            i = i + 1
    return li
 
def bubble_sort_3(li): # mit nur einer Schleife
    count_swap = 0
    i = 0
    while True:
        if li[i+1] < li[i]:
            li[i],li[i+1] = li[i+1],li[i]
            count_swap = count_swap + 1
        if i == len(li) - 2:
            if count_swap == 0:
                return li
            i = 0
            count_swap = 0
        else:
            i = i + 1

Aufgabe 4: Insertionsort (Zusatzaufgabe)

def insertion_sort_1(li): # mit while
    right = 1
    while right < len(li):
        left = 0
        while left < right:
            if li[left] > li[right]:
                li.insert(left,li[right])
                li.pop(right+1)
                break
            left = left + 1
        right = right + 1
    return li
 
def insertion_sort_2(li): # mit for
    for right in range(1,len(li)):
        for left in range(0,right):
            if li[left] > li[right]:
                li.insert(left,li[right])
                li.pop(right+1)
                break
    return li