AP2 Tracker FIAE
0
3 Labor-Module:
Klicke zum Wechseln
Spezialisierung Anwendungsentwicklung (FIAE)

Algorithmen, Sortierverfahren & Effizienz (O-Notation)

In der AP2 (FIAE) sind Algorithmen der absolute Dreh- und Angelpunkt: Vergleich von Sortierverfahren, Binärer Suche, Rekursion und deren mathematischer Laufzeitkomplexität.

O

Was bedeutet die O-Notation in der Prüfung?

Die O-Notation (Landau-Symbol) beschreibt, wie stark die Laufzeit oder der Speicherbedarf wächst, wenn die Datenmenge n größer wird. Sie misst keine Sekunden, sondern die Anzahl der Rechenschritte.

O(1)
Konstant
Immer gleich schnell, egal wie groß n ist (z.B. Array-Zugriff arr[5]).
O(log n)
Logarithmisch
Extrem schnell! Verdoppelt sich n, braucht es nur 1 Schritt mehr (Binäre Suche).
O(n)
Linear
Wächst 1:1 mit den Daten. 1000 Elemente = 1000 Durchläufe (Einfache Schleife).
O(n²)
Quadratisch
Gefährlich langsam bei großen Daten! Schachtelschleifen (Bubble/Selection Sort).

Alle Prüfungs-Algorithmen im Laufzeit-Vergleich

AP2 Pflichtwissen
Algorithmus Best Case Average Case Worst Case In-Place? Stabilität? Wann einsetzen?
Lineare Suche O(1) O(n) O(n) Ja – Unsortierte Daten; kleine Arrays.
Binäre Suche O(1) O(log n) O(log n) Ja – Zwingend sortiertes Array! Bei 1 Mio. Werten max. 20 Schritte.
Bubble Sort O(n)* O(n²) O(n²) Ja Stabil Lehrzwecke; *Best-Case O(n) nur mit getauscht-Flag!
Selection Sort O(n²) O(n²) O(n²) Ja Instabil Minimale Tausch-Anzahl (exakt n Tausche); z.B. bei teurem Flash-Speicher.
Insertion Sort O(n) O(n²) O(n²) Ja Stabil Hervorragend für bereits fast sortierte Daten oder Online-Streams.
QuickSort O(n log n) O(n log n) O(n²) Ja Instabil In der Praxis meist der schnellste Allrounder (Divide & Conquer).

Die 5 FIAE-Sortier- und Suchverfahren im Detail

1. Binäre Suche (Telefonbuch-Methode) O(log n)

Schlage das Buch in der Mitte auf. Ist der gesuchte Name weiter vorne, wirfst du die gesamte rechte Buchhälfte weg. Bei jedem Schritt halbiert sich die Arbeit!

SOLANGE links <= rechts TUE
mitte = (links + rechts) // 2
WENN arr[mitte] == ziel DANN RÜCKGABE mitte
WENN arr[mitte] < ziel DANN links = mitte + 1
SONST rechts = mitte - 1
ENDE SOLANGE
2. Insertion Sort (Kartenspiel-Methode) O(n) bis O(n²)

Wie beim Sortieren von Spielkarten auf der Hand: Du nimmst die nächste Karte, schaust von rechts nach links durch die bereits sortierten Karten und schiebst sie an die passende Stelle.

FÜR i = 1 BIS n - 1
aktuell = arr[i], j = i - 1
SOLANGE j >= 0 UND arr[j] > aktuell TUE
arr[j + 1] = arr[j], j = j - 1
arr[j + 1] = aktuell
3. Selection Sort (Such- & Tausch-Methode) Immer O(n²)

Suche das absolute Minimum im gesamten Rest des Arrays. Wenn du es gefunden hast, tausche es mit dem Element ganz links. Wiederhole das für Position 1, 2, ...

FÜR i = 0 BIS n - 2
minIdx = i
FÜR j = i + 1 BIS n - 1
WENN arr[j] < arr[minIdx] DANN minIdx = j
TAUSCHE arr[i], arr[minIdx]
4. QuickSort (Divide & Conquer) O(n log n)

Wähle ein Vergleichselement (Pivot). Sortiere alle kleineren Zahlen nach links und alle größeren nach rechts. Wende dasselbe rekursiv auf die linke und rechte Hälfte an.

pivot = arr[rechts]
// Partitioniere: alle < pivot nach links
partition(arr, links, rechts)
quickSort(arr, links, pivotIdx - 1)
quickSort(arr, pivotIdx + 1, rechts)

Rekursion & der Call-Stack (Was passiert im RAM?)

Jedes Mal, wenn eine Funktion sich selbst aufruft, reserviert das Betriebssystem einen neuen Stack Frame im Arbeitsspeicher für die lokalen Variablen. Fehlt die Abbruchbedingung (Basisfall), wächst der Stack unendlich, bis der Speicher voll ist: der berüchtigte Stack Overflow!