Suchen und Sortieren [KSR Wiki]

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
====== Suchen und Sortieren ======

Weiter zu [[gf_informatik:suchen_und_sortieren_2023:binaersuche|Binäre Suche]]

Direkt zu [[gf_informatik:suchen_und_sortieren:sortieren|Sortieren]]

==== Einführung ====

{{ :gf_informatik:binary_search.jpeg?nolink&400|}}
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 [[https://dict.leo.org/englisch-deutsch/search|dict.leo.org]] einen Suchbegriff innert Millisekunden zu finden? Wie findet [[https://tel.search.ch/kantonsschule%20romanshorn|tel.search.ch]] den richtigen Eintrag
?
=== Aufgabe A1: Suchen in einem Wörterbuch / Lexikon ===

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?


==== Lineare Suche ====
{{ :gf_informatik:linear_search.png?nolink&400|}}
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.

=== Aufgabe A2: Lineare Suche in Python ===

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

<code python 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']
</code>
  - 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!). 
  - Test: Der Funktionsaufruf `print(linear_search(names,'Haggai'))` soll $4$ ausgeben.
  - 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!)|
  - Gehe IN der Funktion die Liste Element für Element durch.
  - Vergleiche jedes dieser Elemente mit demjenigen, nach dem gesucht wird.
  - Wenn es gleich ist: Gebe die Position vom Element in der Liste zurück.
  - Ausserhalb der Funktion: Lese nun aus der **anderen** Liste das Element mit der eben ermittelten Position aus.
++++


<nodisp 1>
++++Lösung|
<code python>
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])
</code>
++++
</nodisp>

=== Aufgabe A3: Postleitzahlen ===
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 [[https://kantonsschuleromanshorn.sharepoint.com/:u:/s/FSInformatik/EYauYQ0tewJAjEjwPurNva8Bto9Dtk1D-yNgUhrtZkuMJg?e=2uc7N1|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.

<code python>
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))
</code>
<code>
1000 Lausanne, Waadt
</code>

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?
   1. Überprüfe deinen Code, indem du die PLZ deines Wohnortes eingibst.
   1. Welche Postleitzahl hat die Ortschaft Niederbipp?
   1. Wie viele Postleitzahlen gibt es für die Stadt Bern?
   1. Wie viele Postleitzahlen gibt es im Kanton Thurgau?

++++Tipps zu 4 und 5.|
   * Diese Aufgaben löst man ohne die `linear_search`-Funktion.
   * Du kannst die Aufgabe lösen, indem du eine neue Funktion programmierst (die natürlich viele Ähnlichkeiten mit der `linear_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.
++++

<nodisp 1>
++++Lösung ohne Code|

   1. Laufen, Basel-Landschaft
   1. 
   1. 4704
   1. 16
   1. 199

++++
</nodisp>

<nodisp 1>
++++Lösung mit Code|
<code python Aufgabe A3.py>
import plz_data

postleitzahlen = plz_data.postleitzahlen()
ortschaften = plz_data.ortschaften()
kantone = plz_data.kantone()

def linear_search(li, el):
    for i in range(len(li)):
        if li[i] == el:
            return i
    return None

# 1. Wie heisst die Ortschaft mit der ultra-nerdigen Postleitzahl 4242 und in welchem Kanton liegt sie?
index = linear_search(postleitzahlen, 4242)
ort = ortschaften[index]
kanton = kantone[index]
print("{0}, {1}".format(ort, kanton))

# 2. Überprüfe deinen Code, indem du die PLZ deines Wohnortes eingibst.
index = linear_search(postleitzahlen, 8570)
print(ortschaften[index])

# 3. Welche Postleitzahl hat die Ortschaft Niederbipp?
index = linear_search(ortschaften, "Niederbipp")
print(postleitzahlen[index])

# 4. Wie viele Postleitzahlen gibt es für die Stadt Bern?
zaehler =  0
for ort in ortschaften:         # andere Variante: for i in range(len(ortschaften)): if ortschaften[i] == "Thurgau"...
    if ort == "Bern":
        zaehler = zaehler + 1
print(zaehler)

# Wie viele Postleitzahlen gibt es im Kanton Thurgau?
zaehler =  0
for i in range(len(kantone)):   # andere Variante: for k in kantone: if k == "Thurgau"...
    if kantone[i] == "Thurgau": # ...
        zaehler = zaehler + 1
print(zaehler)
</code>

++++
</nodisp>
=== Aufgabe A4: Postleitzahlen plus (optional) ===


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


++++Tipps zu 1.|
Das Problem ist, dass du versuchen musst, Duplikate zu verhindern. Dazu kannst du alle Ortsnamen des Kantons Bern in eine Liste schreiben. Bevor du einen neuen hinzufügst, überprüfst du erst, ob der Name bereits in der Liste vorkommt. Nur wenn nicht, fügst du diesen hinzu.

Code zum Überprüfen, ob ein Element `el` (nicht) bereits in einer Liste `li` vorkommt:
<code python>
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
</code>
++++

++++Tipps zu 2.|
Erstelle zuerst eine Funktion quersumme(x), welche die quersumme der Zahl x zurückgibt: Also zum Beispiel 6 für die Zahl 123. Hierfür hilft fogelende Überlegung: 
  * Wenn du ''123 % 10'' rechnest, erhältst du **3**. Wenn du ''123 %%//%% 10'' rechnest, erhältst du 12: Noch eine Runde: 
  * Wenn du ''12 % 10'' rechnest, erhältst du **2**. Wenn du ''12 %%//%% 10'' rechnest, erhältst du 1: Noch eine Runde: 
  * Wenn du ''1 % 10'' rechnest, erhältst du **1**. Wenn du ''1 %%//%% 10'' rechnest, erhältst du 0: fertig.

Deine Funktion nutzt du, um die Quersummen der Postleizahlen zu berechnen.
++++

++++Lösung ohne Code|
  - 554
  - 70927
++++

++++Lösung mit Code|
<code python>
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)

</code>
++++
=== Aufgabe A5: Postleitzahlen mit Zeitmessung ===
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?

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

<nodisp 1>
++++Lösung|
<code python time_algos.py>
import time
import plz_data


def stopwatch(plz):
    start = time.time()
    index = linear_search(plz_data.postleitzahlen(), plz)
    elapsed = time.time() - start
    print("Lineare Suche für {0} dauerte {1:.0f}s".format(plz, elapsed))

stopwatch(8590)
</code>
++++
</nodisp>

=== Aufgabe A6: Mehrere Suchresultate ===
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:
<code python>
positionen = linear_search2(postleitzahlen,8580)
for p in positionen:
    print(ortschaften[p])
</code>

++++Lösung ohne Code|
  - Sommeri
  - Hagenwil b. Amriswil
  - Hefenhofen
  - Amriswil
++++

<nodisp1>
++++Lösung mit Code|
<code python>
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])

</code>
++++
</nodisp>
=== Aufgabe A7: Verbesserte lineare Suche (optional) ===

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.


=== Aufgabe A8: Besserer Algorithmus? (optional) ===

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 [[gf_informatik:suchen_und_sortieren_2023:binaersuche|Binäre Suche]]