Kako se odločiš med algoritmi sortiranja?

Question

Accepted Answer

Izbira algoritma za sortiranje se zmanjša na nekaj lastnosti: **časovna kompleksnost**, **stabilnost**, **poraba pomnilnika na mestu** in naravo podatkov. Nobeden sam sort ne zmaga povsod.

## Ključne lastnosti

- **Stabilen:** enaki elementi ohranijo svojski relativni vrstni red (potrebno za sortiranje po več ključih).
- **Na mestu:** porabi O(1) ali O(log n) dodatnega pomnilnika.
- **Prilagodljiv:** hitrejši na skoraj sortiranih vhodih.

## Primerjava

| Algoritem | Povpr. čas | Najslabši | Stabilen | Na mestu |
|-----------|----------|-------|--------|----------|
| Insertion | O(n²) | O(n²) | Da | Da |
| Merge | O(n log n) | O(n log n) | Da | Ne |
| Quick | O(n log n) | O(n²) | Ne | Da |
| Heap | O(n log n) | O(n log n) | Ne | Da |

## Navodila

- **Majhno / skoraj sortirano** -> insertion sort.
- **Potrebna stabilnost ali zagotovljeno O(n log n)** -> merge sort.
- **Splošno hitro v pomnilniku, povprečna hitrost je важна** -> quicksort (naključni pivot).
- **Zagotovljena meja + tesna poraba pomnilnika** -> heap sort.

```python
# Most languages ship a tuned hybrid; prefer it in production
sorted(data, key=lambda x: x.priority)   # stable Timsort in Python
```

## Pasti

Ne implementiraj sami sortiranja, razen če imaš konkreten razlog — bibliotečni sortiranja (Timsort, introsort) so preizkušeni hibridi.

## Zakaj je to važno

Prilagajanje sorta podatkom in zahtevam se izogne tako zapravljanju časa kot prikritim hroščem (kot je izguba stabilnosti).

Razumevanje kompromisov pojasni, zakaj so standardne knjižnice izbrale hibride kot Timsort in introsort.

Ta primerjalna presoja — ne pomnjenje enega algoritma — je tisto, kar prava inženirska dela in intervjuji nagrajujejo.

Algoritem	Povpr. čas	Najslabši	Stabilen	Na mestu
Insertion	O(n²)	O(n²)	Da	Da
Merge	O(n log n)	O(n log n)	Da	Ne
Quick	O(n log n)	O(n²)	Ne	Da
Heap	O(n log n)	O(n log n)	Ne	Da