Erklären Sie Bubble Sort, Insertion Sort und Selection Sort

Question

Accepted Answer

Dies sind drei einfache **O(n²)** Vergleichssortierungen. Sie sind langsam bei großen Eingaben, aber leicht zu verstehen und nützlich zum Lehren der Sortierungsmechanik.

## Wie jede funktioniert

- **Bubble Sort:** wiederholtes Vertauschen benachbarter ungeordneter Paare; große Werte "sprudeln" in jedem Durchgang zum Ende.
- **Selection Sort:** finde das Minimum des unsortieren Teils und vertausche es an die richtige Stelle.
- **Insertion Sort:** vergrößere ein sortiertes Präfix durch Einfügen jedes neuen Elements an der richtigen Stelle.

## Beispiel (Insertion Sort)

```python
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]                  # element to place
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]       # shift bigger elements right
            j -= 1
        arr[j + 1] = key              # drop key into the gap
    return arr

insertion_sort([5, 2, 4, 1])          # -> [1, 2, 4, 5]
```

## Vergleich

| Sort | Beste | Schlechteste | Stabil | In-Place |
|------|-------|--------------|--------|----------|
| Bubble | O(n) | O(n²) | Ja | Ja |
| Selection | O(n²) | O(n²) | Nein | Ja |
| Insertion | O(n) | O(n²) | Ja | Ja |

## Wann verwenden / Fallstricke

Insertion Sort ist tatsächlich schnell für **kleine oder fast sortierte** Arrays und wird in Hybrid-Sorters verwendet. Vermeiden Sie alle drei bei großen unsortierten Daten — verwenden Sie stattdessen O(n log n) Sorts.

## Warum es wichtig ist

Diese Sorts bauen Intuition für Invarianten, Vertauschungen und Stabilität auf, bevor Sie sich mit fortgeschrittenen Algorithmen auseinandersetzen.

Insertion Sort taucht insbesondere in Produktions-Sorts (wie Timsort) für winzige Sub-Arrays auf.

Zu wissen, warum sie O(n²) sind, macht den Sprung zu O(n log n) Sorts sinnvoll.

Sort	Beste	Schlechteste	Stabil	In-Place
Bubble	O(n)	O(n²)	Ja	Ja
Selection	O(n²)	O(n²)	Nein	Ja
Insertion	O(n)	O(n²)	Ja	Ja