Sortieralgorithmen: Grundlagen

Algorithmen und Datenstrukturen: Sortieren

• Sortieralgorithmen ordnen eine Menge von Elementen nach einem bestimmten Kriterium an.
• Ziel ist die Korrektheit, Effizienz und einfache Implementierung.

Grundlagen des Sortierens

• Eingabe ist eine Sequenz von n Elementen: $a_1, a_2,..., a_n$.
• Ausgabe ist eine Permutation der Eingangssequenz: $a'_1, a'_2,..., a'_n$, wobei $a'_1 \leq a'_2 \leq... \leq a'_n$ gilt.
• Der Sortierschlüssel ist der Wert, nach dem die Sortierung erfolgt.
• Vergleichsbasierte Algorithmen bestimmen die relative Ordnung durch Vergleiche.
• Nicht-vergleichsbasierte Algorithmen nutzen andere Operationen zur Bestimmung der Ordnung.

In-place Sortieralgorithmen

• Benötigen neben dem Eingabe-Array nur konstanten zusätzlichen Speicher.
• Sind oft schneller, da keine Speicherallokation nötig ist.

Stabilität von Sortieralgorithmen

• Ein stabiler Sortieralgorithmus erhält die relative Reihenfolge von Elementen mit gleichen Sortierschlüsseln.
• Beispiel für stabile Sortierung: $(5, 1)$, $(7, 1)$, $(3, 9)$ wird zu $(5, 1)$, $(7, 1)$, $(3, 9)$ nach Sortierung nach dem zweiten Wert.
• Beispiel für instabile Sortierung: $(5, 1)$, $(7, 1)$, $(3, 9)$ wird zu $(7, 1)$, $(5, 1)$, $(3, 9)$ nach Sortierung nach dem zweiten Wert.

Laufzeit von Sortieralgorithmen

• Die Laufzeit ist abhängig von der Eingabe.
• Best-case: Minimale Laufzeit für eine spezifische Eingabe.
• Average-case: Durchschnittliche Laufzeit über alle möglichen Eingaben.
• Worst-case: Maximale Laufzeit für eine spezifische Eingabe.
• O-Notation: Beschreibt das asymptotische Verhalten der Laufzeit im Worst-case.

Elementare Sortieralgorithmen

• Zu den elementaren Sortieralgorithmen gehören Selection Sort, Insertion Sort und Bubble Sort.

Höhere Sortieralgorithmen

• Zu den höheren Sortieralgorithmen gehören Quicksort, Merge Sort, Heapsort und Radixsort.

Selection Sort: Funktionsweise

• Finde das kleinste Element im Array und tausche es mit dem ersten.
• Finde das zweitkleinste Element und tausche es mit dem zweiten.
• Setze dies fort, bis das gesamte Array sortiert ist.

Selection Sort: Beispiel

• Gegeben: 5 2 8 1 9 4
• Schrittweise Sortierung:
  • 1 2 8 5 9 4 (1. Tausch)
  • 1 2 8 5 9 4 (2. Tausch)
  • 1 2 4 5 9 8 (3. Tausch)
  • 1 2 4 5 9 8 (4. Tausch)
  • 1 2 4 5 8 9 (5. Tausch)

Selection Sort: Eigenschaften

• In-place: Ja
• Stabil: Nein
• Laufzeit: $O(n^2)$ in allen Fällen

Selection Sort: Pseudocode

for i = 0 to n-2 do
    min = i
    for j = i+1 to n-1 do
        if a[j] < a[min] then
            min = j
        end if
    end for
    swap a[i] with a[min]
end for