Suchen und Sortieren

Weiter zu Binäre Suche

Direkt zu Sortieren

Das Ziel einer Suche ist es, in einer grossen Datenmenge möglichst schnell das gesuchte Element zu finden. Beispielsweise suchen wir in einem Lexikon oder Wörterbuch den Eintrag zu einem Begriff, im Telefonbuch die Nummer einer Person oder eines Geschäfts. Heutzutage suchen wir zumeist im Internet - aber wie schafft es dict.leo.org einen Suchbegriff innert Millisekunden zu finden? Wie findet tel.search.ch den richtigen Eintrag ?

Zu zweit oder dritt: Eine Person wählt in einem Wörterbuch oder Lexikon heimlich einen Eintrag, der auf einer Seite rechts oben steht. Das Buch wird geschlossen und eine andere Person versucht mit möglichst wenigen Suchschritten (1x Blättern ist ein Schritt), den Begriff zu finden. Es ist dabei verboten, auf die Markierungen mit den Anfangsbuchstaben an der Seite des Buches zu schauen.

Überlegt euch verschiedene Strategien, wie ihr vorgehen könnt. Welche Strategie benötigt die wenigsten Schritte?

Der einfachste Algorithmus sucht das ganze Buch von vorne nach hinten durch. Allerdings dauert das ziemlich lange. Ist das Buch doppelt so lang, wird die Suche auch doppelt so lange dauern. Wir sprechen deshalb von linearer Suche - der Aufwand steigt linear zusammen mit der Menge der Begriffe.

Betrachte folgenden Datensatz mit Namen und Telefonnummern. Zum Beispiel ist die Telefonnummer von Daniel 0791111111.

lineare_suche.py

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']

1. Implementiere die lineare Suche in einer Funktion linear_search(li,el). Die Funktion soll in der Liste li nach dem Element el suchen. Falls es gefunden wird, soll die Position (Index) des Elements in der Liste zurückgegeben werden (nicht geprintet!).
2. Test: Der Funktionsaufruf print(linear_search(names,'Haggai')) soll $4$ ausgeben.
3. Nutze nun diese Funktion, um die Telefonnummer von 'Micha' zu ermitteln.

Achtung: Generell bei solchen Aufgaben gilt: Verwende keine vordefinierten Suchfunktionen. Es geht genau darum, dass du diese selbst programmierst.

Tipps (zuerst ohne Tipps versuchen!)

def linear_search(li, el):
    for i in range(len(li)):
        if li[i] == el:
            return i
    return None
 
index = linear_search(names, 'Micha')
print(numbers[index])

Für das kleine Propheten-Telefonbuch ist es nicht so wichtig, wie schnell der Such-Algorithmus ist. Was aber, wenn wir ein grösseres Dataset verwenden?

Lade die Datei plz_data.py herunter und speichere sie im selben Verzeichnis wie dein Code. Du kannst die Daten zu Schweizer Postleitzahlen, Ortschaften und Kantonen wie folgt verwenden. Natürlich muss deine linear_search Funktion von Aufgabe 2 vorhanden sein.

import plz_data
 
# Liste aller Schweizer Postleitzahlen:
postleitzahlen = plz_data.postleitzahlen()
# Liste der dazugehörigen Ortschaften
ortschaften = plz_data.ortschaften()
# Liste der dazugehörigen Kantone
kantone = plz_data.kantone()
 
plz = 1000
index = linear_search(postleitzahlen, plz)
ort = ortschaften[index]
kanton = kantone[index]
print("{0} {1}, {2}".format(plz, ort, kanton))

1000 Lausanne, Waadt

Die Listen sind nach Postleitzahlen sortiert.

Löse folgende Teilaufgaben alle in einer Datei. Nutze Kommentare, z.B. # 1 als Überschriften für die einzelnen Teilaufgaben.

1. Wie heisst die Ortschaft mit der ultra-nerdigen Postleitzahl 4242 und in welchem Kanton liegt sie?
2. Überprüfe deinen Code, indem du die PLZ deines Wohnortes eingibst.
3. Welche Postleitzahl hat die Ortschaft Niederbipp?
4. Wie viele Postleitzahlen gibt es für die Stadt Bern?
5. Wie viele Postleitzahlen gibt es im Kanton Thurgau?

Tipps zu 4 und 5.

1. Wie viele verschiedenen Ortsnamen gibt es im Kanton Bern? Beachte, dass es Ortschaften mit mehreren Postleitzahlen und Postleitzahlen mit mehreren Ortsnamen gibt.
2. Bestimme die Summe aller Quersummen von allen vierstelligen Zahlen, welche als Postleitzahl in der Schweiz vergeben sind.

Tipps zu 1.

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

Tipps zu 2.

Lösung ohne Code

Lösung mit Code

import plz_data
 
postleitzahlen = plz_data.postleitzahlen()
ortschaften = plz_data.ortschaften()
kantone = plz_data.kantone()
 
def quersumme(x): 
    cs = 0
    while x > 0:
        cs = cs + x % 10
        x = x // 10
    return cs
 
#1: Wie viele verschiedenen Ortsnamen gibt es im Kanton Bern?
ortsnamen = []
for i in range(len(kantone)):
    if kantone[i] ==  "Bern":
        if not ortschaften[i] in ortsnamen:
            ortsnamen.append(ortschaften[i])
print(len(ortsnamen))
 
#2: Summe aller Quersummen aller Postleitzahl in der Schweiz.
summe = 0
for plz in postleitzahlen:
    summe = summe + quersumme(plz)
print(summe)

Schreibe Python-Code, um zu messen, wie lange die Suche dauert. Um die Zeit zu stoppen, kannst du das time Modul verwenden. Wie lange dauert die Suche für die PLZ 1000 (Lausanne)? Wie lange für 8590 Romanshorn? Weshalb der Unterschied?

import time
start = time.time()
# do something
elapsed = time.time() - start
print("do something took {0}s".format(elapsed))

In der Liste der Postzleitzahlen kommen einige Postleitzahlen mehrmals vor. Zum Beispiel kommt die Postleitzahl 8580 viermal vor. Wenn du aber mit der Funktion linear_search in der Liste der Postzleitzahlen nach 8580 suchst, erhälst du bloss eine Position: Diejenige, an der die Postleitzahl 8580 zum ersten Mal auftaucht. An dieser Position befindet sich in der Ortsnamen-Liste der Eintrag „Sommeri“. Auch Amriswil hat die Postleitzahl 8580, erscheint aber weiter hinten in der Liste.

Erstelle eine neue Funktion linear_search2(li, el). Dazu kopierst du die bestehende und erweiterst sie: Neu soll nicht bloss eine Position zurückgegeben werden, sondern eine Liste mit Positionen. Falls bloss ein Eintrag gefunden wird, enthält die Liste nur ein Element; falls nichts gefunden wird, ist die Liste leer.

Teste die Funktion zum Beispiel so:

positionen = linear_search2(postleitzahlen,8580)
for p in positionen:
    print(ortschaften[p])

Lösung ohne Code

import plz_data
 
postleitzahlen = plz_data.postleitzahlen()
ortschaften = plz_data.ortschaften()
kantone = plz_data.kantone()
 
def linear_search2(li, el):
    results = []
    for i in range(len(li)):
        if li[i] == el:
            results.append(i)
    return results
 
positionen = linear_search2(postleitzahlen,8580)
for p in positionen:
    print(ortschaften[p])

Stelle dir vor, du suchst in der bereits alphabetisch sortierten Liste ['albert','christine','dominick','emma'] nach dem Namen 'barbara'. Sobald du beim Suchen bei 'christine' amkommst, weisst du, dass du abbrechen kannst und der gesuchte Wert (also 'barbara') nicht in der Liste enthalten ist. Achtung: Das geht nur, wenn man sicher weiss, dass die Liste sortiert ist.

Erweitere deine lineare Suche um diese Funktionalität. Füge deiner Funktion dazu ein weiteres Argument mit einem Defaultwert is_sorted = False hinzu. Wenn die Liste nicht sortiert ist, soll die lineare Suche wie bisher ablaufen. Wenn sie sortiert ist, soll sie vorzeitig abbrechen.

Hast du eine Idee für einen besseren, sprich effizienteren Suchalgorithmus einer bereits sortierten Liste? Bespreche mit der Lehrperson und implementiere danach in Python.

Weiter zu Binäre Suche