Forklar bubble sort, insertion sort og selection sort

Question

Accepted Answer

Dette er tre simple **O(n²)** sammenlignings-sorter. De er langsomme på store inputs, men nemme at forstå og nyttige til at undervise i sorterings mekanisme.

## Hvordan hver fungerer

- **Bubble sort:** gentagne gange udveksle usortering tilstødende par; store værdier "bobler" til slutningen hver gang.
- **Selection sort:** find minimumet af den usorterede del og udveksle det på plads.
- **Insertion sort:** vokser et sorteret præfiks ved at indsætte hvert nyt element på det rette sted.

## Eksempel (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]
```

## Sammenligning

| Sort | Bedst | Værst | Stabil | In-place |
|------|-------|-------|--------|----------|
| Bubble | O(n) | O(n²) | Ja | Ja |
| Selection | O(n²) | O(n²) | Nej | Ja |
| Insertion | O(n) | O(n²) | Ja | Ja |

## Hvornår man skal bruge / faldgruber

Insertion sort er genuint hurtig til **små eller næsten-sorterede** arrays og bruges inden i hybrid sorter. Undgå alle tre på stort usorteret data — brug O(n log n) sorter i stedet.

## Hvorfor det betyder noget

Disse sorter opbygger intuition for invarianter, bytninger og stabilitet, før du tackler avancerede algoritmer.

Insertion sort vises især inde i produktions sorter (som Timsort) til små sub-arrays.

At vide hvorfor de er O(n²) gør springet til O(n log n) sorter meningsfuldt.

Sort	Bedst	Værst	Stabil	In-place
Bubble	O(n)	O(n²)	Ja	Ja
Selection	O(n²)	O(n²)	Nej	Ja
Insertion	O(n)	O(n²)	Ja	Ja