Standard-Algorithmen Suche & Sortierung – Lineare/Binäre Suche, BubbleSort, SelectionSort & InsertionSort

Dieser Beitrag ist eine Begriffserklärung zu Such- und Sortieralgorithmen – inklusive Prüfungsfragen und Tags.

In a Nutshell

Diese Standard-Algorithmen dienen dem schnellen Auffinden (Suche) oder der Ordnung (Sortieren) von Daten in Arrays oder Listen. Sie bilden eine prüfungsrelevante Grundlage für algorithmisches Denken.

Kompakte Fachbeschreibung

Lineare und binäre Suche sind elementare Verfahren zum Auffinden eines Wertes in Datenstrukturen. Die lineare Suche prüft jedes Element sequenziell, während die binäre Suche eine sortierte Liste nutzt und die Suche halbiert. Sortieralgorithmen wie Bubble Sort, Selection Sort und Insertion Sort dienen der Reihung von Daten. Bubble Sort vergleicht benachbarte Elemente mehrfach, Selection Sort sucht das kleinste Element und tauscht es nach vorne, Insertion Sort baut eine sortierte Liste sukzessive auf. Diese Algorithmen unterscheiden sich vor allem in Komplexität und Effizienz (Big-O).

Prüfungsrelevante Stichpunkte

• Lineare Suche durchläuft jedes Element sequenziell (O(n))
• Binäre Suche halbiert iterativ den Suchbereich (O(log n), nur bei sortierten Daten)
• Bubble Sort vergleicht und vertauscht Nachbarelemente mehrfach (O(n²))
• Selection Sort sucht jeweils das Minimum und tauscht es nach vorne (O(n²))
• Insertion Sort sortiert durch sukzessives Einfügen (O(n²), aber gut bei fast sortierten Daten)
• Verständnis der Ablauflogik ist prüfungsrelevant (Pseudocode, Dry Run)
• Stabilität, Speicherbedarf und Komplexität unterscheiden sich deutlich

Kernkomponenten

1. Lineare Suche
2. Binäre Suche
3. Bubble Sort
4. Selection Sort
5. Insertion Sort
6. Laufzeitkomplexität (Big-O)
7. Stabilität (Reihenfolge gleichwertiger Elemente)
8. Iterativer Ablauf mit Indexverwaltung
9. Absicherung gegen Indexfehler
10. Dry Run zur Verifikation

Praxisbeispiel

// Beispiel: Insertion Sort
funktion insertionSort(array)
für i von 1 bis array.länge - 1
    key = array[i]
    j = i - 1
    solange j >= 0 und array[j] > key
        array[j + 1] = array[j]
        j = j - 1
    array[j + 1] = key

Erklärung: Das aktuelle Element wird in den sortierten linken Teil einsortiert.

Vorteile und Nachteile

Vorteile

• Einfach zu implementieren und verstehen
• Gut geeignet für kleine oder nahezu sortierte Datensätze
• Stabil (besonders Insertion Sort)

Nachteile

• Ineffizient bei großen Datenmengen (O(n²))
• Bubble und Selection Sort benötigen viele Vergleiche
• Binäre Suche nur bei sortierten Arrays einsetzbar

Typische Prüfungsfragen (mit Kurzantwort)

1. Binäre Suche funktioniert und wann anwendbar? Halbiert iterativ den Suchbereich – nur bei sortierten Daten.
2. Bubble Sort vs. Selection Sort? Bubble Sort vergleicht Nachbarn, Selection Sort sucht Minimum pro Durchlauf.
3. Warum Insertion Sort stabil? Gleiche Werte behalten ihre ursprüngliche Reihenfolge.
4. Bubble Sort Laufzeit im schlechtesten Fall? O(n²), da jedes Element mehrfach verglichen wird.
5. Stabilität bei Sortieralgorithmen bedeutet? Gleichwertige Elemente behalten ihre Reihenfolge.
6. Effizientere Suche bei sortierten Daten? Binäre Suche mit O(log n).
7. Insertion Sort effizient bei fast sortierten Daten? Weil nur wenige Vergleiche und Verschiebungen nötig sind.
8. Algorithmus mit Dry Run prüfen? Durch manuelles Nachvollziehen der Zwischenschritte mit konkreten Daten.

Wichtigste Quellen

1. https://visualgo.net/en/sorting
2. https://www.geeksforgeeks.org/sorting-algorithms
3. https://cs-field-guide.org.nz/en/chapters/algorithms