Paaiškinkite bubble sort, insertion sort ir selection sort.

Question

Accepted Answer

Tai trys paprasti **O(n²)** palyginimo rūšiavimo algoritmai. Jie lėti su didžiais įvestimis, tačiau lengvai suprantami ir naudingi rūšiavimo mechanikai mokyti.

## Kaip veikia kiekvienas

- **Bubble sort:** pakartotinai keičia gretimas neteisinga tvarka esančias poras; didelės reikšmės "burbuliu iškyla" į pabaigą kiekviename peržiūroje.
- **Selection sort:** randa nesurūšytos dalies minimumą ir jį keičia į reikiamą vietą.
- **Insertion sort:** augina surūšytą prefiksą įdėdama kiekvieną naują elementą į teisingą vietą.

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

## Palyginimas

| Sort | Best | Worst | Stable | In-place |
|------|------|-------|--------|----------|
| Bubble | O(n) | O(n²) | Yes | Yes |
| Selection | O(n²) | O(n²) | No | Yes |
| Insertion | O(n) | O(n²) | Yes | Yes |

## Kada naudoti / spąstai

Insertion sort tikrai greitas **mažiems arba beveik surūšytiems** masyvams ir naudojamas hibridiniuose rūšiavimuose. Venkite visų trijų su dideliais nesurūšytais duomenimis — naudokite O(n log n) rūšiavimą.

## Kodėl tai svarbu

Šie rūšiavimai sukuria intuiciją apie invariantus, keitus ir stabilumą, prieš pradėdami dirbti su sudėtingais algoritmais.

Insertion sort ypač pasirodo gamybos rūšiavimuose (tokiuose kaip Timsort) mažiems sub-masyvams.

Supratimas, kodėl jie yra O(n²), daro perėjimą prie O(n log n) rūšiavimo prasmingą.

Sort	Best	Worst	Stable	In-place
Bubble	O(n)	O(n²)	Yes	Yes
Selection	O(n²)	O(n²)	No	Yes
Insertion	O(n)	O(n²)	Yes	Yes