Forklar bubble sort, insertion sort og selection sort.

Question

Accepted Answer

Dette er tre enkle **O(n²)** sammenligningssorteringer. De er trege på store inndatamengder, men enkle å forstå og nyttige for å lære mekanikkene i sortering.

## Hvordan hver fungerer

- **Bubble sort:** bytt gjentatte ganger naboelementer som er i feil rekkefølge; store verdier "bobler" til slutten hver pass.
- **Selection sort:** finn minimum av den usorterte delen og bytt det inn på plass.
- **Insertion sort:** voks et sortert prefiksert ved å sette inn hvert nytt element på riktig 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

| Sortering | Best | Verste | Stabil | In-place |
|-----------|------|--------|--------|----------|
| Bubble | O(n) | O(n²) | Ja | Ja |
| Selection | O(n²) | O(n²) | Nei | Ja |
| Insertion | O(n) | O(n²) | Ja | Ja |

## Når du skal bruke / fallgruver

Insertion sort er genuint raskt for **små eller nesten-sorterte** arrays og brukes inne i hybridsorteringer. Unngå alle tre på store usorterte data — bruk O(n log n) sorteringer i stedet.

## Hvorfor det betyr noe

Disse sorteringene bygger intuisjon for invarianter, bytter og stabilitet før du takler avanserte algoritmer.

Insertion sort dukker særlig opp inne i produksjonssorteringer (som Timsort) for små subarrayer.

Å vite hvorfor de er O(n²) gjør spranget til O(n log n) sorteringer meningsfullt.

Sortering	Best	Verste	Stabil	In-place
Bubble	O(n)	O(n²)	Ja	Ja
Selection	O(n²)	O(n²)	Nei	Ja
Insertion	O(n)	O(n²)	Ja	Ja