Sortier- und Suchalgorithmen verstehen und vergleichen

lock
Bevorstehend

Lerne die wichtigsten Sortier- und Suchalgorithmen kennen, vergleiche ihre Effizienz und verstehe, wo sie im Alltag eingesetzt werden.

Ziele dieses Moduls
  • Sie können Bubble Sort und Binäre Suche erklären und deren Funktionsweise nachvollziehen
    Verstehen
  • Sie können verschiedene Sortier- und Suchalgorithmen hinsichtlich ihrer Effizienz analysieren und vergleichen
    Analysieren
  • Sie können begrĂĽnden, wann welcher Algorithmus in der Praxis am besten geeignet ist
    Evaluieren

EinfĂĽhrung

Computer müssen ständig Daten sortieren und durchsuchen: Google sortiert Suchergebnisse, Spotify sortiert Playlists, Instagram sortiert deinen Feed. Aber wie funktioniert das eigentlich?

In diesem Modul lernen Sie die wichtigsten Algorithmen kennen und können deren Effizienz vergleichen.

Was ist ein Sortier-Algorithmus?

Ein Sortier-Algorithmus ordnet eine Liste von Elementen in eine bestimmte Reihenfolge (z.B. aufsteigend).

Beispiele aus dem Alltag:

  • Kontakte im Handy nach Namen sortiert
  • YouTube-Videos nach Beliebtheit sortiert
  • E-Mails nach Datum sortiert

Es gibt viele verschiedene Sortier-Algorithmen – manche sind schnell, andere langsam. Warum gibt es dann überhaupt verschiedene? Das werden Sie gleich herausfinden!

Bubble Sort – Der einfachste Algorithmus

Funktionsweise:

  1. Vergleiche immer zwei benachbarte Elemente
  2. Wenn das linke grösser ist als das rechte → tausche sie
  3. Wiederhole, bis die Liste sortiert ist

Visualisierung: Schauen Sie sich Bubble Sort auf VisualGo.net an!

Warum heisst es "Bubble Sort"? Die grössten Elemente "blubbern" wie Blasen nach oben!

Challenge

Aufgabe 1: Bubble Sort mit Karten

Material: 10 Spielkarten (oder Zahlen-Kärtchen)

Auftrag:

  1. Mische die Karten
  2. Sortiere sie nach der Bubble Sort-Regel
  3. Zähle: Wie viele Vergleiche hast du gemacht?
  4. Zähle: Wie viele Tausch-Operationen hast du gemacht?

Frage zum Nachdenken: Was wĂĽrde passieren, wenn du 100 Karten sortieren mĂĽsstest?

Checklist

0/4

Andere Sortier-Algorithmen

Bubble Sort ist langsam bei grossen Datenmengen. Deshalb gibt es bessere Algorithmen:

  • Quick Sort: Teile die Liste in kleinere Teile und sortiere diese (sehr schnell!)
  • Merge Sort: Teile die Liste, sortiere getrennt, fĂĽge zusammen
  • Selection Sort: Suche immer das kleinste Element und setze es an den Anfang

Tool: Vergleiche die Algorithmen auf VisualGo.net

Challenge

Aufgabe 2: Algorithmen-Vergleich

Ă–ffne VisualGo.net und vergleiche die Algorithmen:

  1. Wähle Bubble Sort → starte mit 10 Elementen → zähle die Schritte
  2. Wähle Quick Sort → starte mit 10 Elementen → zähle die Schritte
  3. Teste beide mit 50 Elementen
  4. Teste beide mit 100 Elementen

FĂĽlle diese Tabelle aus:

Algorithmus10 Elemente50 Elemente100 Elemente
Bubble Sort___ Schritte___ Schritte___ Schritte
Quick Sort___ Schritte___ Schritte___ Schritte

Checklist

0/4

Suchalgorithmen: Lineare vs. Binäre Suche

Stell dir vor, du suchst ein Wort im Wörterbuch. Würdest du bei A anfangen und jede Seite durchblättern? Oder schlägst du ungefähr in der Mitte auf?

Lineare Suche:

  • Schaue jedes Element von vorne bis hinten an
  • Langsam, aber funktioniert immer

Binäre Suche:

  • Liste muss sortiert sein!
  • Schaue in die Mitte → zu gross? Linke Hälfte durchsuchen. Zu klein? Rechte Hälfte durchsuchen.
  • Sehr schnell!

Beispiel: Zahl zwischen 1-100 erraten

  • Lineare Suche: 1, 2, 3, 4, ... → bis zu 100 Versuche
  • Binäre Suche: 50, 25, 12, ... → maximal 7 Versuche!

Challenge

Aufgabe 3: Binary Search Game

Ă–ffne das Binary Search Visualizer

Challenge:

  1. Lass den Computer sich eine Zahl zwischen 1-100 denken
  2. Versuche sie mit linearer Suche zu finden (1, 2, 3, ...)
  3. Versuche sie mit binärer Suche zu finden (50, dann halbieren)

Fragen:

  • Wie viele Versuche brauchst du mit linearer Suche?
  • Wie viele Versuche brauchst du mit binärer Suche?
  • Was ist der maximale Unterschied?

Checklist

0/4

Note

Algorithmen in der realen Welt

Wo werden diese Algorithmen eingesetzt?

  • Google: Sortiert Milliarden Suchergebnisse (Merge Sort)
  • Netflix: Sortiert Filme nach deinem Geschmack (Quick Sort)
  • Telefonbuch-App: Findet Kontakte blitzschnell (Binäre Suche)
  • Instagram: Sortiert deinen Feed (komplexe Algorithmen)

Wichtig zu wissen: In der Praxis werden oft hybride Algorithmen verwendet – eine Kombination aus mehreren!

Reflection

Reflexion

Denken Sie ĂĽber folgende Fragen nach:

  1. Warum gibt es nicht "den einen besten" Sortier-Algorithmus?
  2. Wann wĂĽrden Sie Bubble Sort verwenden? Wann Quick Sort?
  3. Warum muss die Liste für binäre Suche sortiert sein?
  4. Wo begegnen Ihnen Sortier- und Suchalgorithmen im Alltag?
  5. Was bedeutet "Effizienz" bei Algorithmen?

Diskutieren Sie Ihre Antworten mit einem Partner oder einer Partnerin.

Challenge

Zusatzaufgabe: Sortier-Algorithmus in Python (Optional)

Programmiere Bubble Sort in Python:

zahlen = [64, 34, 25, 12, 22, 11, 90]

# Deine Aufgabe: Implementiere Bubble Sort!
# Tipp: Du brauchst zwei verschachtelte Schleifen

for i in range(len(zahlen)):
    for j in range(len(zahlen) - i - 1):
        # Hier kommt dein Code
        pass

print(zahlen)  # Sollte sortiert sein!

Erweiterung: Miss die Zeit mit import time und vergleiche mit Pythons eingebautem sorted()!