Razloži bubble sort, insertion sort in selection sort.

Question

Accepted Answer

To so tri preprosti **O(n²)** primerjalni algoritmi za sortiranje. So počasni pri velikih vhodih, vendar lahki za razumevanje in uporabni za poučevanje mehanike sortiranja.

## Kako vsak deluje

- **Bubble sort:** večkrat zamenjaj sosedne pare, ki niso v redu; velike vrednosti se "mehurčasto" premaknejo na konec v vsakem prehodu.
- **Selection sort:** najdi minimum neusopanega dela in ga zamenjaj na mesto.
- **Insertion sort:** povečaj sortirani predpona z vstavljanjem vsakega novega elementa na pravo mesto.

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

## Primerjava

| Sortiranje | Najboljše | Najslabše | Stabilno | Na mestu |
|------------|-----------|----------|---------|----------|
| Bubble | O(n) | O(n²) | Da | Da |
| Selection | O(n²) | O(n²) | Ne | Da |
| Insertion | O(n) | O(n²) | Da | Da |

## Kdaj uporabiti / pasti

Insertion sort je res hiter za **majhne ali skoraj sortirane** nize in se uporablja v hibridnih sortirih. Izogni se vsem trem pri velikih neusopaenih podatkih — namesto tega uporabi O(n log n) sortiranja.

## Zakaj je to pomembno

Ta sortiranja gradijo intuicijo za invariante, zamenjave in stabilnost, preden se lotite naprednejših algoritmov.

Insertion sort se pojavi v produkcijskih sortirih (kot je Timsort) za majhne podceli.

Razumevanje, zakaj so O(n²), naredi preskok na O(n log n) sortiranja smiselnim.

Sortiranje	Najboljše	Najslabše	Stabilno	Na mestu
Bubble	O(n)	O(n²)	Da	Da
Selection	O(n²)	O(n²)	Ne	Da
Insertion	O(n)	O(n²)	Da	Da