Spiega bubble sort, insertion sort e selection sort.

Question

Accepted Answer

Questi sono tre semplici **O(n²)** algoritmi di ordinamento per confronto. Sono lenti su input grandi ma facili da capire e utili per insegnare la meccanica dell'ordinamento.

## Come funziona ciascuno

- **Bubble sort:** scambia ripetutamente coppie adiacenti fuori ordine; i valori grandi "risalgono" alla fine ad ogni passata.
- **Selection sort:** trova il minimo della parte non ordinata e lo scambia in posizione.
- **Insertion sort:** sviluppa un prefisso ordinato inserendo ogni nuovo elemento nella sua posizione corretta.

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

## Confronto

| 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 |

## Quando usare / insidie

Insertion sort è genuinamente veloce per array **piccoli o quasi ordinati** ed è usato dentro gli algoritmi ibridi. Evita tutti e tre su dati grandi non ordinati — usa invece algoritmi O(n log n).

## Perché è importante

Questi algoritmi costruiscono intuizione su invarianti, scambi e stabilità prima di affrontare algoritmi avanzati.

Insertion sort in particolare appare dentro gli algoritmi di ordinamento in produzione (come Timsort) per piccoli sottovettori.

Capire perché sono O(n²) rende significativo il salto agli algoritmi O(n log n).

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