Objasnite bubble sort, insertion sort i selection sort.

Question

Accepted Answer

Ovo su tri jednostavna **O(n²)** sort-a sa poređenjem. Sporosti su na velikim unosima ali laki za razumijevanje i korisni za nastavu mehanike sortiranja.

## Kako svaki funkcionira

- **Bubble sort:** više puta zamijenite susjedne parove koji nisu u redoslijedu; velike vrijednosti "mjehuraju" do kraja svakog prolaza.
- **Selection sort:** pronađite minimum nesortirane dijela i zamijenite ga na mjestu.
- **Insertion sort:** povećajte sortirani prefiks tako što ćete svaki novi element umetnuti na pravo mjesto.

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

## Usporedba

| Sort | Najbolji | Najgori | Stabilan | Na mjestu |
|------|------|-------|--------|----------|
| Bubble | O(n) | O(n²) | Da | Da |
| Selection | O(n²) | O(n²) | Ne | Da |
| Insertion | O(n) | O(n²) | Da | Da |

## Kada koristiti / nedostaci

Insertion sort je zaista brz za **male ili gotovo sortirane** nizove i koristi se unutar hibridnih sortiranja. Izbjegavajte sva tri na velikim nesortiranima — umjesto toga koristite O(n log n) sortiranja.

## Zašto je važno

Ovi sortiranja grade intuiciju za invarijante, zamjene i stabilnost prije nego što se pozabavite naprednim algoritmima.

Insertion sort se naročito pojavljuje unutar proizvodnih sortiranja (poput Timsort) za male podnizove.

Znanje zašto su O(n²) čini skok na O(n log n) sortiranja značajnim.

Sort	Najbolji	Najgori	Stabilan	Na mjestu
Bubble	O(n)	O(n²)	Da	Da
Selection	O(n²)	O(n²)	Ne	Da
Insertion	O(n)	O(n²)	Da	Da