🧮 Algorithmen verstehen

1. Was ist ein Algorithmus?

Ein Algorithmus ist eine eindeutige Folge ausführbarer Schritte, die Eingaben verarbeitet und zu einem gewünschten Ergebnis führt. Er beschreibt die Lösung unabhängig davon, in welcher Programmiersprache sie später umgesetzt wird.

Algorithmen begegnen uns überall

• Eine Navigation berechnet eine geeignete Route.
• Ein Onlineshop sortiert Produkte nach Preis oder Relevanz.
• Eine Tabellenkalkulation verarbeitet Daten nach Formeln und Regeln.
• Eine Suchfunktion prüft Datensätze auf einen passenden Wert.
• Kompressions- und Verschlüsselungsverfahren transformieren Informationen.

2. Eigenschaften eines guten Algorithmus

Eine bloße Liste von Anweisungen reicht nicht. Ein brauchbarer Algorithmus sollte mehrere Qualitätsmerkmale erfüllen.

3. Eingabe – Verarbeitung – Ausgabe

Das EVA-Prinzip hilft, ein Problem in drei übersichtliche Bereiche zu zerlegen.

EINGABE preis, ist_stammkunde

WENN ist_stammkunde = wahr DANN
    endpreis ← preis × 0,90
SONST
    endpreis ← preis
ENDE WENN

AUSGABE endpreis

Vor dem Programmieren klären

• Welche Eingaben sind erlaubt?
• Welche Ausgabe wird genau erwartet?
• Welche Sonderfälle können auftreten?
• Wann soll der Ablauf enden?
• Woran wird die Korrektheit geprüft?

4. Einen Algorithmus darstellen

Algorithmen können auf verschiedene Weise beschrieben werden. Die passende Darstellung hängt von Zielgruppe, Komplexität und Entwicklungsphase ab.

Beispiel: größere von zwei Zahlen

EINGABE a, b

WENN a > b DANN
    AUSGABE a
SONST
    AUSGABE b
ENDE WENN

5. Sequenz, Auswahl und Wiederholung

Sehr viele Algorithmen lassen sich aus drei grundlegenden Kontrollstrukturen zusammensetzen.

wasser_einfüllen
wasser_erhitzen
kaffee_aufgießen

WENN temperatur > 90 DANN
    heizung_ausschalten
SONST
    weiter_erhitzen

FÜR jede zahl IN zahlen
    summe ← summe + zahl
ENDE FÜR

6. Wichtige Algorithmen-Typen

7. Lineare Suche

Die lineare Suche prüft Elemente der Reihe nach, bis der Zielwert gefunden wurde oder das Ende erreicht ist. Sie funktioniert auch mit unsortierten Daten.

FUNKTION lineare_suche(liste, ziel)
    FÜR index VON 0 BIS länge(liste) - 1
        WENN liste[index] = ziel DANN
            RÜCKGABE index
        ENDE WENN
    ENDE FÜR

    RÜCKGABE -1
ENDE FUNKTION

Wann ist sie sinnvoll?

• Die Daten sind klein oder unsortiert.
• Es wird nur selten gesucht.
• Die Reihenfolge darf nicht verändert werden.
• Eine einfache, gut verständliche Lösung ist wichtiger als maximale Geschwindigkeit.

8. Binäre Suche

Die binäre Suche vergleicht den Zielwert mit dem mittleren Element. Danach wird nur in der passenden Hälfte weitergesucht. Dafür müssen die Daten nach derselben Ordnung sortiert sein.

FUNKTION binaere_suche(liste, ziel)
    links ← 0
    rechts ← länge(liste) - 1

    SOLANGE links <= rechts
        mitte ← ganzzahl((links + rechts) / 2)

        WENN liste[mitte] = ziel DANN
            RÜCKGABE mitte
        SONST WENN liste[mitte] < ziel DANN
            links ← mitte + 1
        SONST
            rechts ← mitte - 1
        ENDE WENN
    ENDE SOLANGE

    RÜCKGABE -1
ENDE FUNKTION

9. Sortieren mit Bubble Sort

Bubble Sort vergleicht benachbarte Elemente und vertauscht sie, wenn sie in der falschen Reihenfolge stehen. Nach jedem vollständigen Durchlauf befindet sich mindestens ein großes Element an seiner endgültigen Position.

FUNKTION bubble_sort(zahlen)
    n ← länge(zahlen)

    FÜR i VON 0 BIS n - 2
        wurde_vertauscht ← falsch

        FÜR j VON 0 BIS n - i - 2
            WENN zahlen[j] > zahlen[j + 1] DANN
                VERTAUSCHE zahlen[j] MIT zahlen[j + 1]
                wurde_vertauscht ← wahr
            ENDE WENN
        ENDE FÜR

        WENN wurde_vertauscht = falsch DANN
            ABBRUCH
        ENDE WENN
    ENDE FÜR

    RÜCKGABE zahlen
ENDE FUNKTION

10. Quicksort – Teile und Herrsche

Quicksort ist ein effizienter, vergleichsbasierter Sortieralgorithmus. Er wählt ein Pivot-Element und teilt die Liste so auf, dass alle kleineren Elemente links und alle größeren rechts stehen. Dann werden beide Teile rekursiv sortiert.

FUNKTION quicksort(zahlen, links, rechts)
    WENN links < rechts DANN
        p ← partition(zahlen, links, rechts)
        quicksort(zahlen, links, p - 1)
        quicksort(zahlen, p + 1, rechts)
    ENDE WENN
ENDE FUNKTION

FUNKTION partition(zahlen, links, rechts)
    pivot ← zahlen[rechts]
    i ← links - 1

    FÜR j VON links BIS rechts - 1
        WENN zahlen[j] <= pivot DANN
            i ← i + 1
            VERTAUSCHE zahlen[i] MIT zahlen[j]
        ENDE WENN
    ENDE FÜR

    VERTAUSCHE zahlen[i + 1] MIT zahlen[rechts]
    RÜCKGABE i + 1
ENDE FUNKTION

11. Merge Sort – Stabile Sortierung

Merge Sort teilt die Liste in zwei Hälften, sortiert jede Hälfte rekursiv und führt sie dann sortiert zusammen. Er ist stabil und hat eine garantierte Laufzeit von O(n log n).

FUNKTION merge_sort(zahlen)
    WENN länge(zahlen) <= 1 DANN
        RÜCKGABE zahlen
    ENDE WENN

    mitte ← länge(zahlen) / 2
    links ← zahlen[0:mitte]
    rechts ← zahlen[mitte:länge(zahlen)]

    links_sortiert ← merge_sort(links)
    rechts_sortiert ← merge_sort(rechts)

    RÜCKGABE merge(links_sortiert, rechts_sortiert)
ENDE FUNKTION

FUNKTION merge(links, rechts)
    ergebnis ← []
    SOLANGE links UND rechts
        WENN links[0] <= rechts[0] DANN
            ergebnis.hinzufügen(links.entferne_erstes())
        SONST
            ergebnis.hinzufügen(rechts.entferne_erstes())
        ENDE WENN
    ENDE SOLANGE

    RÜCKGABE ergebnis + links + rechts
ENDE FUNKTION

12. Heapsort – Sortieren mit Heap

Heapsort nutzt eine Heap-Datenstruktur (Binärbaum) zum Sortieren. Er baut zunächst einen Max-Heap auf und entfernt dann sukzessive das größte Element.

FUNKTION heap_sort(zahlen)
    n ← länge(zahlen)

    FÜR i VON n/2 - 1 BIS 0
            heapify(zahlen, n, i)
    ENDE FÜR

    FÜR i VON n - 1 BIS 1
        VERTAUSCHE zahlen[0] MIT zahlen[i]
        heapify(zahlen, i, 0)
    ENDE FÜR

    RÜCKGABE zahlen
ENDE FUNKTION

FUNKTION heapify(zahlen, n, i)
    grösste ← i
    links ← 2 * i + 1
    rechts ← 2 * i + 2

    WENN links < n UND zahlen[links] > zahlen[grösste] DANN
        grösste ← links
    ENDE WENN

    WENN rechts < n UND zahlen[rechts] > zahlen[grösste] DANN
        grösste ← rechts
    ENDE WENN

    WENN grösste ≠ i DANN
        VERTAUSCHE zahlen[i] MIT zahlen[grösste]
        heapify(zahlen, n, grösste)
    ENDE WENN
ENDE FUNKTION

13. Rekursion verstehen

Eine rekursive Funktion löst ein Problem, indem sie eine kleinere Version desselben Problems aufruft. Jede Rekursion benötigt einen Basisfall, der weitere Aufrufe beendet.

FUNKTION fakultaet(n)
    WENN n = 0 DANN
        RÜCKGABE 1          # Basisfall
    ENDE WENN

    RÜCKGABE n × fakultaet(n - 1)
ENDE FUNKTION

Für fakultaet(4) entstehen die Aufrufe 4 × 3 × 2 × 1 × fakultaet(0). Der Basisfall liefert 1 und beendet die Kette.

14. Dynamische Programmierung

Dynamische Programmierung löst komplexe Probleme, indem sie sie in überlappende Teilprobleme zerlegt und die Ergebnisse zwischenspeichert (Memoization).

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

15. Greedy-Algorithmen

Greedy-Algorithmen treffen in jedem Schritt die lokal beste Entscheidung, in der Hoffnung, dass dies zur global optimalen Lösung führt.

FUNKTION muenzwechsel(betrag, münzen)
    ergebnis ← []
    münzen ← sortiere_absteigend(münzen)

    FÜR jede münze IN münzen
        während betrag >= münze
            ergebnis.hinzufügen(münze)
            betrag ← betrag - münze
        ENDE WÄHREND
    ENDE FÜR

    RÜCKGABE ergebnis
ENDE FUNKTION

16. Backtracking

Backtracking ist eine systematische Suchmethode, die alle möglichen Lösungen durchprobiert und bei Sackgassen zurückspringt.

FUNKTION n_damen(n, reihe, damen)
    WENN reihe = n DANN
        RÜCKGABE damen           # Lösung gefunden
    ENDE WENN

    FÜR spalte VON 0 BIS n - 1
        WENN konflikt_frei(reihe, spalte, damen) DANN
            damen[reihe] ← spalte
            ergebnis ← n_damen(n, reihe + 1, damen)
            WENN ergebnis ≠ NULL DANN
                RÜCKGABE ergebnis
            ENDE WENN
        ENDE WENN
    ENDE FÜR

    RÜCKGABE NULL               # Keine Lösung gefunden
ENDE FUNKTION

17. Divide-and-Conquer

Divide-and-Conquer (Teile und Herrsche) zerlegt ein Problem in kleinere Teilprobleme, löst sie rekursiv und setzt die Lösungen zusammen.

18. Big O – wie wächst der Aufwand?

Die Big-O-Notation beschreibt vereinfacht, wie stark Laufzeit oder Speicherbedarf mit wachsender Eingabegröße n zunehmen. Sie nennt keine exakten Sekunden.

Warum Konstanten trotzdem zählen

Zwei Verfahren mit derselben Big-O-Klasse können in der Praxis unterschiedlich schnell sein. Programmiersprache, Datenstruktur, Speicherzugriffe, Eingabeverteilung und konstante Faktoren bleiben relevant. Big O ist ein Werkzeug für das Wachstum, nicht die vollständige Leistungsbewertung.

19. Algorithmen in Python und JavaScript

Lineare Suche in Python

def lineare_suche(werte, ziel):
    for index, wert in enumerate(werte):
        if wert == ziel:
            return index
    return -1


zahlen = [8, 3, 14, 7, 21]
print(lineare_suche(zahlen, 14))  # 2

Binäre Suche in JavaScript

function binaereSuche(werte, ziel) {
    let links = 0;
    let rechts = werte.length - 1;

    while (links <= rechts) {
        const mitte = Math.floor((links + rechts) / 2);

        if (werte[mitte] === ziel) {
            return mitte;
        }

        if (werte[mitte] < ziel) {
            links = mitte + 1;
        } else {
            rechts = mitte - 1;
        }
    }

    return -1;
}

const zahlen = [3, 7, 12, 18, 25, 31, 42];
console.log(binaereSuche(zahlen, 25)); // 4

Bubble Sort in Python

def bubble_sort(werte):
    ergebnis = werte.copy()
    n = len(ergebnis)

    for i in range(n - 1):
        wurde_vertauscht = False

        for j in range(n - 1 - i):
            if ergebnis[j] > ergebnis[j + 1]:
                ergebnis[j], ergebnis[j + 1] = ergebnis[j + 1], ergebnis[j]
                wurde_vertauscht = True

        if not wurde_vertauscht:
            break

    return ergebnis


print(bubble_sort([9, 4, 7, 2, 8, 1]))

20. Interaktives Suchlabor

Vergleiche lineare und binäre Suche Schritt für Schritt. Für die binäre Suche muss die Zahlenliste aufsteigend sortiert sein.

21. Interaktives Bubble-Sort-Labor

Beobachte, wie Bubble Sort benachbarte Zahlen vergleicht und bei Bedarf vertauscht. Grün markierte Bereiche sind bereits endgültig einsortiert.

22. Fibonacci-Vergleich: Rekursiv vs. Iterativ

Dieses Labor zeigt den dramatischen Performance-Unterschied zwischen rekursiver und iterativer Implementierung der Fibonacci-Folge.

23. Den passenden Algorithmus auswählen

Es gibt selten einen Algorithmus, der für jede Situation am besten ist. Eine gute Entscheidung berücksichtigt Anforderungen und Daten gemeinsam.

1. 1
   Problem präzisierenWelche Eingaben, Ausgaben und fachlichen Regeln sind verbindlich?
2. 2
   Daten verstehenWie groß sind sie, sind sie sortiert und wie häufig ändern sie sich?
3. 3
   Grenzfälle sammelnLeere Eingabe, doppelte Werte, ungültige Daten und sehr große Mengen berücksichtigen.
4. 4
   Einfache korrekte Lösung bauenVerständlichkeit und Testbarkeit bilden die erste stabile Grundlage.
5. 5
   Messen und vergleichenMit realistischen Daten prüfen, ob Laufzeit oder Speicher tatsächlich problematisch sind.
6. 6
   Gezielt optimierenNur den nachgewiesenen Engpass verbessern und Korrektheit erneut testen.

24. Checkliste für einen zuverlässigen Algorithmus

Hake die erledigten Punkte ab. Die Auswahl bleibt nur während dieses Seitenaufrufs erhalten.

0 von 10 Punkten erledigt

25. Häufige Fehler und Lösungen

26. Übungen zum Mitmachen

Löse die Aufgaben zuerst in Alltagssprache oder Pseudocode und übertrage sie anschließend in eine Programmiersprache.

Lösungshinweise

27. Passende nächste Themen

Diese Grundlagen-Seiten vertiefen die praktische Umsetzung und die Wahl geeigneter Datenmodelle.

28. Häufige Fragen zu Algorithmen