Sortieralgorithmen

Bubble Sort

Beim Bubble Sort werden benachbarte Elemente verglichen und vertauscht, wenn sie in der falschen Reihenfolge sind. Dieser Vorgang wiederholt sich, bis die Liste sortiert ist.

Eigenschaften:

• Einfach zu verstehen
• Ineffizient bei großen Datenmengen
• Laufzeit: O(n²)

Pseudocode:

function bubbleSort(liste):
    wiederhole
        vertauscht = false
        für i von 0 bis liste.länge - 2:
            wenn liste[i] > liste[i + 1]:
                tausche(liste[i], liste[i + 1])
                vertauscht = true
    bis nicht vertauscht

Selection Sort

Selection Sort sucht in jedem Durchlauf das kleinste Element aus dem unsortierten Teil und tauscht es an die richtige Position.

Eigenschaften:

• Stabil und einfach
• Weniger Tauschvorgänge als Bubble Sort
• Laufzeit: O(n²)

Pseudocode:

function selectionSort(liste):
    für i von 0 bis liste.länge - 1:
        minIndex = i
        für j von i + 1 bis liste.länge - 1:
            wenn liste[j] < liste[minIndex]:
                minIndex = j
        tausche(liste[i], liste[minIndex])

Insertion Sort

Insertion Sort baut die sortierte Liste schrittweise auf, indem jeweils ein Element an der richtigen Stelle im bereits sortierten Teil eingefügt wird.

Eigenschaften:

• Gut für kleine oder fast sortierte Daten
• Laufzeit: O(n²), aber effizient bei fast sortierten Daten

Pseudocode:

function insertionSort(liste):
    für i von 1 bis liste.länge - 1:
        key = liste[i]
        j = i - 1
        während j ≥ 0 und liste[j] > key:
            liste[j + 1] = liste[j]
            j = j - 1
        liste[j + 1] = key

Typische Prüfungsfragen

• Erläutern Sie den Ablauf des Bubble Sort anhand eines Beispiels.
• Welche Vorteile bietet Insertion Sort bei fast sortierten Daten?
• Warum benötigt Selection Sort weniger Tauschvorgänge als Bubble Sort?
• Wann ist Insertion Sort anderen einfachen Sortieralgorithmen überlegen?