Algorithmen II: Suchen & 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.
====== - Algorithmen II: Suchen & Sortieren ======

++++Lernziele|

Prüfungsrelevant ist alles, was in den Lektionen und Übungen behandelt wurde. Die Lernziele unten dienen als Gradmesser und sind nicht unbedingt komplett.

   * Erkläre, die Idee hinter der **linearen Suche**.
   * Erkläre, die Idee hinter der **binären Suche**.
   * Warum heissen die lineare und binäre Suche jeweils so?
   * Erkläre, welche **Bedingungen** die Daten erfüllen müssen, damit man die lineare resp. binäre Suche anwenden kann.
   * Berechne die Anzahl Suchschritte im **Worst Case** für die beiden Suchfunktionen.
   * Vergleiche die **Performance** der beiden Suchfunktionen.
   * **Implementiere** die beiden Suchfunktionen selbst in Python.
   * Mit Suchalgorithmen Datensätze **durchgehen** und nach Informationen suchen.

   * Erkläre, wie der **Selection Sort** funktioniert.
   * Erkläre, wie der **Bubble Sort** funktioniert.
   * Wende diese Sortieralgorithmen **von Hand** auf einen Datensatz an.
   * **Programmiere** die beiden Sortieralgorithmen.

++++

===== - Suchen =====
{{ :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 ist die **lineare Suche** sucht das ganze Buch von vorne nach hinten durch. Dabei wird jedes Element solange mit dem gesuchten verglichen, bis man es gefunden hat.

=== Aufgabe A2: Effizienz der linearen Suche ===

   * Wie effizient ist dieser Algorithmus?
   * Warum heisst dieser Algorithmus //lineare// Suche?


=== Aufgabe A3: Lineare Suche in Python ===

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

<code python>
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>

   1. Implementiere die lineare Suche in einer Funktion `linear_search(li,el)`. Darin soll in der Liste li nach dem Element el gesucht werden. Falls es gefunden wird, soll die Position (Index) des Elements in der Liste zurück gegeben werden (*nicht* geprintet!). Test: Der Funktionsaufruf `print(linear_search(names,'Haggai'))` soll $4$ ausgeben.\\ \\
   1. 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 (versuche zuerst ohne lösen)|
   1. Gehe IN der Funktion die Liste Element für Element durch.
   1. Vergleiche jedes dieser Elemente mit demjenigen, nach dem gesucht wird.
   1. Sobald es gefunden wurde: Gebe die Position vom Element in der Liste zurück.
   1. Greife nun (ausserhalb der Funktion) auf das Element an dieser Position in der *anderen* Liste zu.
++++

=== Aufgabe A4: Postleitzahl ===

Der {{ :gf_informatik:plz_data.py.zip |PLZ-Datensatz}} beinhaltet drei lange Listen mit sämtlichen Postleitzahlen, den zugehörigen Ortschaften und Kantonen.

++++Datensatz laden|
Der Datensatz ist in einem ZIP-File. Lade dieses herunter und entzippe es (typischerweise: rechte Maustaste / Hier entpacken). Erst nachher ist es verwendbar.
++++

Beispielsweise sind von allen drei Listen die Einträge an Position 7: PLZ: 1009 , Ortschaft: Pully, Kanton: Waadt.
Dies bedeutet also, dass die Ortschaft Pully die Postzleitzahl 1009 hat und im Kanton Waadt liegt.

Schreibe deine eigene lineare Suche, um die Fragen unten zu beantworten. Löse alle Teilaufgaben im *gleichen File*. 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, in dem du die PLZ deines Wohnortes eingibst.
   1. Welche Postleitzahl hat die Ortschaft Niederbipp?
   1. Wie viele Postleitzahlen gibt für die Stadt Zürich?
   1. Wie viele Postleitzahlen gibt für den Kanton Thurgau?
   1. Wie viele verschiedenen Ortsnamen gibt es im Kanton Zürich? Beachte, dass es Ortschaften mit mehreren Postleitzahlen und Postleitzahlen mit mehreren Ortsnamen gibt. Unten findest du noch Tipps zu dieser Aufgabe.
   1. **Sinnbefreite Zusatzaufgabe:** Bestimme die Summe aller Quersummen von allen vierstelligen Zahlen, welche als Postleitzahl in der Schweiz vergeben sind.


++++Tipps zu 4. & 5.|

   * 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.


++++

++++Tipps zu 6.|
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:
<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>

++++

++++Lösungen ohne Code|

   1. Laufen Basel-Landschaft
   1. Weinfelden Thurgau
   1. 4704 Bern
   1. 27
   1. 199
   1. 263
   1. 70927

++++

=== Aufgabe A5: Verbesserte lineare Suche (optional) ===

Stelle dir vor, du suchst in der bereits *alphabetisch sortierten* Liste `['albert','christine','dominick','emma']` nach dem `'bert'`. Sobald du beim Suchen also bei `'christine'` angelangst, weisst du, dass du *abbrechen* kannst und der gesuchte Wert (also `'bert'`) 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 A6: 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.


==== - Binäre Suche ====

{{ :gf_informatik:binary_search.png?nolink&400| }}

Ist ein Datensatz nicht sortiert, macht eine lineare Suche Sinn. Ist dieser aber bereits sortiert, so gibt es viel effizientere Suchalgorithmen, wie die hier beschriebene **binäre Suche**:

Wir teilen den Suchbereich ungefähr in der Mitte. Ist der Begriff zufälligerweise gleich dort, haben wir den Eintrag gefunden; ist der Begriff kleiner als das gefundene Element, suchen wir in der ersten Hälfte, sonst in der zweiten Hälfte weiter, bis genau ein einziges Element übrig bleibt. An dieser Stelle befindet sich der gesuchte Begriff, wenn er überhaupt vorhanden ist. Falls nicht, würde er an dieser Stelle eingefügt werden.

Bei der Suche im Wörterbuch suchen wir zu Beginn nur die richtige Seite - wir teilen den Suchbereich indem wir die Mitte der verbleibenden Seiten wählen und den ersten Eintrag der Seite anschauen. Sind wir auf der richtigen Seite, wiederholen wir dasselbe mit den einzelnen Einträgen.

=== Aufgabe B1: Binäre Suche im Wörterbuch ===

Setzte euch in kleinen ($2-4$) Gruppen zusammen und arbeitet mit einem Wörterbuch:

   * Jemand in der Gruppe sucht ein zufälliges Wort aus.
   * Eine andere Person sucht dieses Wort mithilfe der binären Suche.
   * Zählt dabei, wie oft ihr blättern (resp. die Seiten aufteilen) müsst.
   * Wie oft müsstet ihr Blättern mit der linearen Suche?
   * Für ein beliebiges Wort: Was ist eine durchschnittliche Anzahl Teilungen, um auf die richtige Seite zu gelangen?
   * Wer in der Klasse musste am häufigsten Blättern? Ist dies überhaupt möglich? Wir werden sehen ...

=== Aufgabe B2: Binäre Suche berechnen ===

   1. Eine Broschüre hat 8 Seiten und du möchtest mithilfe der binären Suche eine bestimmte Seite finden. Wie oft musst du //im worst case// blättern? Tipp: Zeichne auf einem Blatt vor dir 8 Striche, die die Seiten repräsentieren.
   1. Wie sieht es mit einer Broschüre mit 16 oder 32 Seiten aus? Wie mit einem Buch mit 256 Seiten?
   1. Erkennst du ein Schema in den letzten zwei Aufgaben?
   1. Du liest gern dicke Fantasy-Bücher. Mit wie oft blättern kannst du eine beliebige Seite finden?
   1. Stelle dir vor, es gäbe ein Telefonbuch für alle $8$ Milliarden Menschen, wobei jede Person eine einzelne Seite hätte. Wie oft musst du hier maximal blättern, um eine beliebige Person zu finden?

=== Aufgabe B3: Binäre Suche in Python ===

**Ziel:** Die binäre Suche in einer Funktion `binary_search(li,el)` implementieren. Die Funktion soll den Index von Element `el` in der Liste `li` zurückgeben. Kommt das Element nicht vor, soll `None` zurückgegeben werden.

Vorgehen:
   * Arbeitet in 2er Gruppen
   * Überlegt euch, wie ihr den Algorithmus implementieren könnt.
   * Legt die ausgeteilten Papierchen mit Nummern sortiert auf den Tisch. Arbeitet mit diesen, um eure Ideen auszuprobieren.
   * Implementiert die Suche. Starte mit dem Code-Template unten.

Schreibt man eine Funktion, so ist es wichtig, diese **gut zu testen**. Am besten tests du jeweils gleichzeitig mehrere Fälle, wie im folgenden Template gezeigt:
<code python>
def binary_search(li,el):
    # write your code here
    pass

# TEST YOUR FUNCTION
print(binary_search(['A','C','D','G','J','N','Q','X'],'B')) # output must be: None
print(binary_search(['A','C','D','G','J','N','Q','X'],'A')) # output must be: 0
print(binary_search(['A','C','D','G','J','N','Q','X'],'C')) # output must be: 1
print(binary_search(['A','C','D','G','J','N','Q','X'],'D')) # output must be: 2
print(binary_search(['A','C','D','G','J','N','Q','X'],'G')) # output must be: 3
print(binary_search(['A','C','D','G','J','N','Q','X'],'J')) # output must be: 4
print(binary_search(['A','C','D','G','J','N','Q','X'],'N')) # output must be: 5
print(binary_search(['A','C','D','G','J','N','Q','X'],'Q')) # output must be: 6
print(binary_search(['A','C','D','G','J','N','Q','X'],'X')) # output must be: 7
print(binary_search(['A','C','D','G','J','N','Q','X'],'Z')) # output must be: None
</code>

++++Tipps|
   * 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.
++++


=== Aufgabe B4: Postleitzahlen ===

   1. In wie vielen Schritten findest du jede Postleitzahl im worst case?
   1. Wende deine binäre Suche auf den Datensatz mit den Postleitzahlen an. Wie heissen die Ortschaften mit der vorgegebenen Postleitzahlen und in welchen Kantonen liegen sie?
     1. 1234
     1. 9100


=== Aufgabe B5: Nach Orten suchen ===

Was passiert, wenn du statt nach Postleitzahlen nach Orten suchst? Funktioniert die Binärsuche? Weshalb nicht? Was müssten wir ändern, damit sie funktioniert?

=== Aufgabe B6: Rekursion (optionale Zusatzaufgabe) ===

Bei der binären Suche gehen wir ja wie folgt vor:
  - Index in der Mitte des Suchintervalls wählen.
  - Element in der Mitte auslesen.
  - Ist dieses Element das richtige, so sind wir fertig.
  - Andernfalls wiederholen wir die Suche mit einem kleineren Teilintervall: left oder right entsprechend anpassen un zurück zu Schritt 1.

Schreibe eine neue Funktion, `binary_search_recursive(L,x,left=None,right=None)`. Die Funktion codiert die obigen Schritte - statt einer `while`-Schleife soll //sich Funktion im Schritt 4 wieder selber aufrufen//. Dieses Verfahren heisst **Rekursion**.

Wahrscheinlich ist dir das `left=None,right=None` in der Deklaration der Funktion aufgefallen: Es bedeutet, dass wenn die Funktion ohne die diese letzten beiden Elemente aufgerufen werden, also z.B. `binary_search_recursive([0,2,4,6,8],2)`, so werden den Variablen `left` und `right` jeweils der Wert `None` zugewiesen.

Rekursion eignet sich für viele Probleme, die sich mit _Divide & Conquer_ (_Teile & Herrsche_) lösen lassen: Probleme, die wir für den trivialen Fall mit einem Element lösen können, und die wir effizient von einem grösseren in ein kleineres Problem überführen können.

===== - Sortieren =====

=== Aufgabe 1: Sortieren ===

**Material:** Kärtchen mit Zahlen

   * Lege die Kärtchen in zufälliger Reihenfolge vor dich auf den Tisch.
   * Sortiere dann die Kärtchen mit einer klaren //Systematik//
   * Regeln:
     * Du darfst nur die beiden Zeigefinger verwenden.
     * Diese kannst du bei Kärtchen positionieren. Du darfst immer nur Kärtchen anschauen, bei denen ein Zeigefinger ist.
     * Es sind zwei Bewegungen von Kärtchen erlaubt.
       * Kärtchen, bei denen Zeigefinger ist, vertauschen.
       * Kärtchen, bei denen Zeigefinger ist, auf neue Ebene bringen.
   * Wie gehst du vor? Notiere stichwortartig.
   * Versuche verschiedene Sortier-Strategien zu finden. Notiere jede Strategie stichwortartig.

=== Aufgabe 2: Selectionsort ===

++++Theorie|
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.
   1. Positioniere deinen linken Zeigefinger beim ersten Kärtchen.
   1. Positioniere deinen rechten Zeigefinger beim Kärtchen rechts daneben.
   1. Ist das rechte Kärtchen kleiner? Falls ja, vertausche die beiden.
   1. 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.
   1. Nach diesem ersten Durchlauf weisst du, dass das Kärtchen ganz links das kleinste ist.
   1. Bewege deinen linken Finger nun um eins nach rechts.
   1. Wiederhole die Schritte ab 3. solange, bis du mit dem linken Finger rechts angekommen bist.
   1. Jetzt sollten die Kärtchen korrekt sortiert sein.

++++

== Teil I ==

Arbeite wieder mit den Buchstaben-Kärtchen: Lege diese in zufälliger Reihenfolge auf den Tisch. Wende dann den Selectionsort-Algorithmus an, um diese zu sortieren.

== Teil II: Python ==

Implementieren den Selectionsort-Algorithmus in Python. Schreibe dazu eine Funktion `selectionsort(l)`. Diese nimmt eine unsortierte Liste `l` entgegen und sortiert diese mit dem Selectionsort-Algorithmus.

Test: Wende deinen Sortieralgorithmus auf einige Listen an:

   * `['K', 'F', 'G', 'I', 'H', 'D', 'B', 'C', 'A', 'E']`
   * `['C', 'D', 'K', 'I', 'H', 'A', 'G', 'B', 'E', 'F']`

++++Tipps (versuche zuerst ohne zu lösen)|

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

<code python>
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
</code>

   * 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.

++++

=== Zusatzaufgabe: Zufallsliste erzeugen ===

Schreibe einen Code, der dir eine Zufallsliste z.B. von Buchstaben erzeugt: `random_list(10)` gibt dir dann eine Liste mit 10 Grossbuchstaben in zufälliger Reihenfolge zurück.

Diese Liste kannst du dann verwenden, um deine Sortieralgorithmen zu testen.


=== Aufgabe 3: Bubblesort ===

++++Theorie|

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?

++++

== Teil I ==

Arbeite wieder mit den Zahlen-Kärtchen: Lege diese in zufälliger Reihenfolge auf den Tisch. Wende dann den Bubblesort-Algorithmus an, um diese zu sortieren.

== Teil II: Python ==

Implementieren den Bubblesort-Algorithmus in Python. Schreibe dazu eine Funktion `bubblesort(L)`. Diese nimmt eine unsortierte Liste `li` entgegen und sortiert diese mit dem Bubblesort-Algorithmus.

++++Tipps|
   - 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]`
   - Wiederhole nun den 1. Schritt mehrfach, bis die Liste sortiert wurde.
   - 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.
   - Man kann den Bubble Sort auch mit nur einer einzigen while-Schleife programmieren, das ist aber eher etw. anspruchsvoller.
++++


=== Aufgabe 4: Insertionsort (Zusatzaufgabe) ===

++++Theorie|
   - 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.
   - Betrachte nun das dritte Element und füge es in der bereits sortierten Teilliste am korrekten Platz ein.
   - Gehe weiter zum vierten Element usw.
++++

Implementiere den Insertionsort-Algorithmus in Python.

++++Tipps|

   * Verwende [[gf_informatik:programmieren_ii_sca#schleifen_abbrechen_optional|break um eine Schleife abzubrechen]]

++++



===== - Lösungen =====

==== - Lösungen Suchen ====

++++Lösungen Suchen|

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

<code python>
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])
</code>

=== Aufgabe A4 ===

Lösungen:

   1. ('Laufen', 'Basel-Landschaft')
   1. ('Weinfelden', 'Thurgau')
   1. (4704, 'Bern')
   1. 27
   1. 199
   1. 263
   1. 70927

Code dazu:
<code python>
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)
</code>

=== Aufgabe A5 ===

<code python>
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
</code>

=== 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
   1. 16 Seiten: max. 5x, 32: 6x, 256: 9x
   1. Buch mit $2^n$ Seiten $\rightarrow$ maximal $(n+1)\times$ blättern
   1. Bücher mit $513-1024$ Seiten: max 11x, da $2^{10} = 1024$
   1. $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 ===

<code python>
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
</code>

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

<code python>
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)
</code>

++++

==== - Lösungen Sortieren ====

++++Lösungen Sortieren|

=== Aufgabe 2: Selection Sort ===

<code python>

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
</code>

=== Zusatzaufgabe: Zufallsliste erzeugen ===

<code python>
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))
</code>


=== Aufgabe 3 ===

<code python>
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
</code>

=== Aufgabe 4: Insertionsort (Zusatzaufgabe) ===

<code python>
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
</code>

++++