Selitä bubble sort, insertion sort ja selection sort

Question

Accepted Answer

Nämä ovat kolme yksinkertaista **O(n²)** vertailusorttia. Ne ovat hitaita suurissa syötteissä, mutta helppo ymmärtää ja hyödylliset lajittelumekaniikan opettamiseen.

## Kuinka kukin toimii

- **Bubble sort:** vaihda toistuvasti vierekkäisiä väärässä järjestyksessä olevia pareja; suuret arvot "kuplituvat" loppuun jokaisella kierroksella.
- **Selection sort:** etsi lajittelemattoman osan minimi ja vaihda se paikoilleen.
- **Insertion sort:** kasvata lajiteltua etuliitettä lisäämällä jokainen uusi elementti oikealle paikalleen.

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

## Vertailu

| Lajittelu | Paras | Huonoin | Vakaa | In-place |
|-----------|-------|---------|-------|----------|
| Bubble | O(n) | O(n²) | Kyllä | Kyllä |
| Selection | O(n²) | O(n²) | Ei | Kyllä |
| Insertion | O(n) | O(n²) | Kyllä | Kyllä |

## Milloin käyttää / Sudenkuopat

Insertion sort on todella nopea **pienille tai lähes lajitelluille** taulukoille ja sitä käytetään hybridisorteissa. Vältä kaikkia kolmea suurissa lajittelemattomissa tiedoissa — käytä sen sijaan O(n log n) -sorteja.

## Miksi se on tärkeää

Nämä sortit rakentavat intuitiota invarianteista, vaihdoista ja vakaasta järjestyksestä ennen kuin ryhdyt edistyneisiin algoritmeihin.

Insertion sort erityisesti näkyy tuotantosortissa (kuten Timsort) pienille ali-ryhmille.

Tiedon siitä, miksi ne ovat O(n²), tekee hyppyn O(n log n) -sorteihin merkitykselliseksi.

Lajittelu	Paras	Huonoin	Vakaa	In-place
Bubble	O(n)	O(n²)	Kyllä	Kyllä
Selection	O(n²)	O(n²)	Ei	Kyllä
Insertion	O(n)	O(n²)	Kyllä	Kyllä