Q1.2 – Algorithmik systematisch aufbauen

Algorithmik betrachtet Verfahren problemorientiert: Welche Voraussetzungen braucht ein Verfahren? Welche Schritte sind zentral? Wie verändert sich der Aufwand bei größeren Datenmengen?

Dieselbe algorithmische Idee kann in verschiedenen Darstellungen erklärt werden. Q1.2 übernimmt die in E3 aufgebauten Darstellungsformen und nutzt sie systematisch.

int minimum(int[] a) {
    int min = a[0];
    for (int i = 1; i < a.length; i++) {
        if (a[i] < min) min = a[i];
    }
    return min;
}

int linearSearch(int[] a, int key) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == key) return i;
    }
    return -1;
}

Lineare Suche: Referenzverfahren ohne Vorbedingungen

boolean linearSuche(int[] a, int schluessel) {
    int i = 0;
    while (i < a.length && a[i] != schluessel) {
        i++;
    }
    return i < a.length;
}

Die Strategie ist robust und allgemein einsetzbar: Ein Element nach dem anderen wird geprüft. Die Zahl der Vergleiche wächst jedoch direkt mit der Datenmenge.

Binäre Suche: effizient durch Halbierung des Suchbereichs

boolean binaereSuche(int[] a, int schluessel) {
    int links = 0, rechts = a.length - 1;
    while (links <= rechts) {
        int mitte = (links + rechts) / 2;
        if (a[mitte] == schluessel) return true;
        if (a[mitte] < schluessel) links = mitte + 1;
        else rechts = mitte - 1;
    }
    return false;
}

Sortieren bedeutet algorithmisch: Eine Folge so umordnen, dass eine definierte Reihenfolge entsteht. Dabei sind Strategie und Kosten verschieden – etwa beim Aufbau eines sortierten Bereichs, beim Suchen eines Minimums oder beim lokalen Vertauschen benachbarter Werte.

Effizienz wird in Q1.2 als fachliche Beobachtung aufgebaut: Wie viele Vergleiche entstehen? Wie viele Verschiebungen oder Tauschoperationen sind nötig? Wie verändert sich das Verhalten bei größeren Eingaben?

Differenzierte Fallanalyse am Beispiel lineare Suche

Die drei Fälle zeigen: Effizienz ist nicht nur „eine Zahl“, sondern hängt von der Eingabesituation ab. Für fundierte Bewertung werden Best-, Worst- und Average-Case gemeinsam betrachtet.

Kausale Effizienzerklärung (Ursache → Wirkung)

• Lineare Suche braucht bis zu n Schritte: Pro Durchlauf wird nur genau ein neues Element ausgeschlossen.
• Binäre Suche braucht etwa logarithmische Laufzeit: Pro Schritt fällt ungefähr die Hälfte des aktuellen Intervalls weg.
• Einfache Sortierverfahren sind oft quadratisch: Ein äußerer Durchlauf über n Positionen kombiniert sich mit inneren Vergleichen/Verschiebungen.

Kausale Lesart: Bei der linearen Suche kann im ungünstigen Fall jedes Element geprüft werden (n Vergleiche). Bei der binären Suche wird der Bereich pro Schritt halbiert (log n Schritte). Einfache iterative Sortierer benötigen häufig verschachtelte Wiederholungen – dadurch entsteht oft eine quadratische Tendenz (n²).

Mini-Vergleich: Bei n = 8 sind lineare 8 Prüfungen vs. binär ca. 3 Schritte plausibel; bei n = 1000 etwa 1000 vs. ca. 10. Der strategische Unterschied wächst mit der Datenmenge.

Auf erhöhtem Niveau kommt mit effizienten Sortieralgorithmen (z. B. Quicksort im Tool) ein Verfahren hinzu, das im Mittel deutlich besser skaliert als die einfachen n²-Verfahren.

Das Werkzeug Such- und Sortieralgorithmen visualisieren wird in Q1.2 als Beobachtungsraum genutzt:

• Schrittweise Ablaufbeobachtung von linearer/binärer Suche sowie Insertion/Quicksort.
• Metriken für Vergleiche und Tausch-/Verschiebeoperationen.
• Vergleichsfläche mit gespeicherten Kurvenverläufen über mehrere Läufe.

Arbeitsauftrag: Führe pro Verfahren Läufe mit identischer Array-Größe durch, dokumentiere die Vergleichswerte und begründe die beobachteten Unterschiede mit der jeweiligen Strategie.

Aufbauend auf Q1.2 erweitert Q1.3 den Algorithmusbegriff um rekursive Modellierung. Im Fokus stehen dann:

• Rekursion als Strukturprinzip mit Anker und Rekursionsschritt,
• iterativ vs. rekursiv als Vergleichsperspektive im selben Problemraum,
• Teile-und-herrsche und präzisierte Effizienzreflexion.

Konkrete Brücke: Die in Q1.2 analysierte binäre Suche zeigt bereits die zentrale Teilproblemstruktur der Rekursion: „Löse dasselbe Problem auf einem kleineren Intervall“. Q1.3 formalisiert genau dieses Muster mit Basisfall und rekursivem Schritt.