Leg bubble sort, insertion sort en selection sort uit.

Question

Accepted Answer

Dit zijn drie eenvoudige **O(n²)** vergelijkingssorteringen. Ze zijn langzaam voor grote invoer, maar gemakkelijk te begrijpen en nuttig voor het onderwijs in sorteersmechanismen.

## Hoe elk werkt

- **Bubble sort:** herhaaldelijk aangrenzende elementen in verkeerde volgorde omwisselen; grote waarden "bubbelen" naar het einde van elke pass.
- **Selection sort:** het minimum van het ongesorteerde deel zoeken en in plaats omwisselen.
- **Insertion sort:** een gesorteerd voorvoegsel vergroten door elk nieuw element op de juiste plek in te voegen.

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

## Vergelijking

| Sort | Best | Worst | Stabiel | In-place |
|------|------|-------|---------|----------|
| Bubble | O(n) | O(n²) | Ja | Ja |
| Selection | O(n²) | O(n²) | Nee | Ja |
| Insertion | O(n) | O(n²) | Ja | Ja |

## Wanneer gebruiken / valkuilen

Insertion sort is werkelijk snel voor **kleine of bijna-gesorteerde** arrays en wordt gebruikt binnen hybride sorteringen. Vermijd alle drie op grote ongesorteerde gegevens — gebruik in plaats daarvan O(n log n) sorteringen.

## Waarom het belangrijk is

Deze sorteringen bouwen intuïtie op voor invarianten, omwisselingen en stabiliteit voordat je geavanceerde algoritmen aanpakt.

Insertion sort verschijnt vooral in productiesorteringen (zoals Timsort) voor kleine subarrays.

Begrijpen waarom ze O(n²) zijn, maakt de sprong naar O(n log n) sorteringen betekenisvol.

Sort	Best	Worst	Stabiel	In-place
Bubble	O(n)	O(n²)	Ja	Ja
Selection	O(n²)	O(n²)	Nee	Ja
Insertion	O(n)	O(n²)	Ja	Ja