Algorithmen — sortieren, suchen und den Aufwand einschätzen
In der Prüfung zählt weniger das Auswendiglernen von Code als die Frage: Welches Verfahren ist hier sinnvoll, und wie verhält sich der Aufwand bei größeren Datenmengen?
Was ein Algorithmus ist
Eine eindeutige Verarbeitungsvorschrift: endlich, ausführbar, determiniert und allgemeingültig. Ein Programm ist die Umsetzung eines Algorithmus in einer Sprache.
Suchen
| Verfahren | Voraussetzung | Aufwand |
|---|---|---|
| Lineare Suche | keine — geht jeden Eintrag durch | O(n) |
| Binäre Suche | Daten sortiert, Direktzugriff (Array) | O(log n) |
Beispiel: In 1.000 sortierten Einträgen braucht die binäre Suche maximal 10 Schritte (210 ≈ 1024), die lineare im schlimmsten Fall 1.000. Vorher sortieren lohnt sich also — aber nur, wenn oft gesucht wird.
Sortieren
| Verfahren | Prinzip | Aufwand (typisch) | Anmerkung |
|---|---|---|---|
| Bubble Sort | Nachbarn tauschen, bis nichts mehr passt | O(n²) | anschaulich, für echte Daten zu langsam |
| Insertion Sort | jeden Wert in den sortierten Teil einfügen | O(n²), bei fast sortiert O(n) | gut für kleine/nahezu sortierte Mengen |
| Selection Sort | wiederholt das kleinste Element suchen | O(n²) | wenige Tauschvorgänge |
| Merge Sort | teilen, sortieren, zusammenfügen | O(n log n) | stabil, gut vorhersagbar |
| Quick Sort | Teilen um ein Pivot-Element | Ø O(n log n), worst case O(n²) | in der Praxis sehr schnell |
| Heap Sort | Sortieren über einen Haufen (Heap) | O(n log n) | kein zusätzlicher Speicherbedarf |
Stabil bedeutet: gleiche Werte behalten ihre ursprüngliche Reihenfolge — relevant, wenn nach mehreren Kriterien sortiert wird.
O-Notation verstehen
Sie beschreibt, wie der Aufwand mit der Eingabegröße wächst — nicht Sekunden:
- O(1) konstant — Direktzugriff im Array.
- O(log n) logarithmisch — binäre Suche, balancierter Baum.
- O(n) linear — eine Schleife über alle Elemente.
- O(n log n) gute Sortierverfahren.
- O(n²) quadratisch — zwei verschachtelte Schleifen, Bubblesort.
- O(2ⁿ) exponentiell — Rucksackproblem (optimale Lösung), wächst unbrauchbar.
Datenstrukturen
| Struktur | Prinzip | Einsatz |
|---|---|---|
| Array | feste Reihenfolge, Direktzugriff über Index | schneller Zugriff, feste Größe |
| Verkettete Liste | Elemente zeigen aufeinander | häufiges Einfügen/Löschen |
| Stapel (Stack) | LIFO — zuletzt rein, zuerst raus | Rückgängig-Funktion, Aufrufstack |
| Warteschlange (Queue) | FIFO — zuerst rein, zuerst raus | Druckaufträge, Nachrichtenpuffer |
| Baum | hierarchisch, binärer Suchbaum sortiert | Suche und Sortierung in O(log n) |
| Hash-Tabelle | Schlüssel wird auf Index abgebildet | sehr schnelle Suche, Reihenfolge egal |
Typische Prüfungsfallen
- Binäre Suche ohne Sortierung: funktioniert nicht — die Voraussetzung wird gern überlesen.
- LIFO und FIFO vertauschen: Stack = LIFO, Queue = FIFO.
- O-Notation als Zeitangabe lesen: Sie beschreibt Wachstum, nicht Millisekunden.
- Quick Sort ist nicht immer schnell: bei bereits sortierten Daten mit schlechtem Pivot droht O(n²).
Weiter üben
Das Grundlagenwissen steht hier frei — geübt wird in der Lernplattform: über 1.300 Prüfungsfragen mit ausführlicher Erklärung zu jeder Antwort, Fortschritt im eigenen Konto.
Passende Videos
Externer Inhalt, geöffnet in einem neuen Tab. Keine Einbettung — solange du nicht selbst klickst, werden keine Daten an YouTube übertragen.