Förklara bubble sort, insertion sort och selection sort.

Question

Accepted Answer

Dessa är tre enkla **O(n²)** jämförelsesortningar. De är långsamma på stora inmatningar men enkla att förstå och användbara för att lära sig sorteringsmekanikmens grundvalar.

## Hur varje fungerar

- **Bubble sort:** byt upprepade gånger angränsande element som är i fel ordning; stora värden "bubblar" till slutet varje varv.
- **Selection sort:** hitta minimivärdet i den osorterade delen och byt det på plats.
- **Insertion sort:** utöka ett sorterat prefix genom att infoga varje nytt element på rätt plats.

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

## Jämförelse

| Sortering | Bäst | 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 |

## När man ska använda / fallgropar

Insertion sort är faktiskt snabb för **små eller nästan sorterade** arrayer och används inuti hybridsortningar. Undvik alla tre på stora osorterade data — använd istället O(n log n) sortningar.

## Varför det är viktigt

Dessa sortningar bygger intuition för invarianter, byten och stabilitet innan du tacklar mer avancerade algoritmer.

Insertion sort förekommer särskilt inuti produktionssorteringar (som Timsort) för små subarrayer.

Att förstå varför de är O(n²) gör steget till O(n log n) sortningar meningsfullt.

Sortering	Bäst	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