Suchen und Sortieren

• Ich kann erklären, wie die lineare Suche und wie die binäre Suche funktioniert.
• Ich kann die beiden Such-Algorithmen (linar und binär) miteinander vergleichen, d.h. Unterschiede, Vor- und Nachteile/Voraussetzungen erklären.

  • Ich kann für eine gegebene Anzahl Einträge (Listen-Länge) die maximale Anzahl Suchanfragen für beide Such-Algorithmen berechnen.
  • Ich kann eine Funktion linear_search(list, value) definieren, die nach der linearen Suche die Position von value in list zurückgibt.
  • Ich kann eine Funktion binary_search(list, value) definieren, die nach der binären Suche die Position von value in list zurückgibt.

  ==== Einführung ==== 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 tel.search.ch den richtigen Eintrag?

  Lineare Suche

  Gäb si mir wenigschtens d Vorwahl
  Per favore
  De gäbs nume no zäh Millione Kombinatione, ja
  079 het si gseit
  „Du weisch immer no nüt“, het si gseit
  Nidmau tschüss het si gseit, ey
  Und i frage si ob ig ihri - tüt tüt tüt het si gseit, tüt tüt 079 by Lo & Leduc

  Der Sänger von 079 will die Telefonnummer der Angebeteten unter allen möglichen Schweizer Mobilfunknummern (10-stellig) mit dem Präfix 079 herausfinden. Dafür probiert er sämtliche Nummern von 079 000 00 00 bis 079 999 99 99 durch, was natürlich ziemlich lange dauert… #### Aufgabe A1 - 079

  Tipp: Höre oder lese den Liedtext genau (Original, Hochdeutsch, Youtube)!

  1. Wie viele Telefonnummern muss der Sänger von 079 durchprobieren?
  2. Wie lange dauert das Probieren einer Telefonnummer?
  3. Wie lange dauert die Suche nach der richtigen Nummer bei 079?
  4. Wieso dauert es so lange? Was ist die Rechnung, die hinter der genannten Dauer steckt?
  5. Wie lange dauerte die Suche, wenn wir nicht einmal die Vorwahl kennen würden (aber wüssten, dass alle Nummern mit 0 beginnen)?

  Algorithmus

  Der einfachste Such-Algorithmus probiert alle Telefonnummern von der kleinsten zur grössten durch. Die Zeit für die Suche steigt proportional mit der Anzahl möglichen Nummern an - wir sagen auch, dass die Zeit linear mit der Grösse des Suchbereichs wächst, und sprechen von Linearer Suche.

  Würden wir statt 079 nicht einmal die Vorwahl kennen, wäre die Suche nochmals zwei Dezimalstellen länger (wenn alle Telefonnummern mit 0 beginnen). Wir müssten also statt 6.5 sogar über 600 Jahre suchen.

  

  Aufgabe A2: Lineare Suche in Python

  Betrachte folgenden Datensatz mit Namen und Telefonnummern. Wir haben zwei parallele Listen, die erste mit Namen, die zweite mit den dazugehörigen Telefonnummern. Am gleichen Index ist in der ersten Liste der Name, in der zweiten die Telefonnummer gespeichert.

  Zum Beispiel finden für den Index 1 Anela in names[1] und ihre Nummer 0790000001 in numbers[1].

  lineare_suche.py

  names = ['Aja', 'Anela', 'Arwen', 'Isra',
           'Juno', 'Kaida', 'Loelia', 'Luna',
           'Lumiel', 'Lyanna', 'Meyra', 'Miriel',
           'Narcissa', 'Nisha', 'Runa', 'Yuna']
  numbers = ['0790000000', '0790000001', '0790000002', '0790000003',
             '0790000004', '0790000005', '0790000006', '0790000007',
             '0790000008', '0790000009', '0790000010', '0790000011',
             '0790000012', '0790000013', '0790000014', '0790000015']

  1. Schreibe eine Python-Funktion linear_search(l, v). Die Funktion soll in der Liste l nach dem Wert v suchen. Falls er gefunden wird, soll die Position (Index) des Elements in der Liste zurückgegeben werden (nicht geprintet!).
  2. Test: Der Funktionsaufruf print(linear_search(names, 'Anela')) soll $1$ ausgeben.
  3. Nun wissen wir, dass die gesuchte Dame Lyanna (die Geheimnisvolle) heisst. Nutze nun diese Funktion, um die Telefonnummer von 'Lyanna' 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 l alle möglichen Indices (Positionen) durch.
• Vergleiche das Element an jedem Index mit dem gesuchten Wert v.
• Wenn es gleich ist: Gib den Index zurück.
• Ausserhalb der Funktion: Lese nun aus der anderen Liste das Element mit dem eben ermittelten Index aus.

  <nodisp 2> ++++Lösung

  def linear_search(l, v):
      for i in range(len(l)):
          if l[i] == v:
              return i
      return None
   
  index = linear_search(names, 'Lyanna')
  print(numbers[index])

  </nodisp>

Aufgabe A3: Zäh Millione Kombinatione

Für das kleine Telefonbuch oben ist es nicht so wichtig, wie schnell der Such-Algorithmus ist. Was aber, wenn wir wirklich alle 10 Millionen Kombinationen durchprobieren?

Für diese Aufgabe benötigst du zusätzlich eine weitere Python-Datei, null79.py, die wir in unserem selbstgeschriebenen Code importieren. Dazu verwenden wir ähnlich wie zu Turtle-Zeiten das Schlüsselwort import:

from null79 import names, numbers

Damit das funktioniert, muss die Datei null79.py im gleichen Ordner gespeichert sein, wie unser selbstgeschriebener Code.

Mit WebtigerPython

Am einfachsten geht das mit diesem WebtigerPython-Link - die Datei ist hier bereits hinterlegt.

Aufgabe A3.py

from null79 import names, numbers
 
def linear_search(l, v):
    for i in range(len(l)):
        if l[i] == v:
            return i
    return None
 
name = 'Lyanna'
idx = linear_search(names, name)
if idx == None:
    print("Du weisch immer no nüt het si gseit")
else:
    tel = numbers[idx]
    print("Die Telefonnummer von " + name + " ist " + tel)
    print("144 hei si gseit!")
    print("Wie isch das nume passiert, hei si gseit.")
    print("Hueresiech, hei si gseit, ey")

Xassemb