Ordinamenti per confronto
Insertion, merge, quick e heap sort decidono l’ordine confrontando coppie di chiavi. Nel modello generale richiedono Ω(n log n) confronti nel caso peggiore.
Algoritmi · Ordinamento
Algoritmi di ordinamento
Non esiste un ordinamento migliore in assoluto. Distribuzione delle chiavi, memoria disponibile, stabilità e forma dell’input determinano la scelta. Ogni scheda apre un simulatore che rende visibili confronti, spostamenti e strutture ausiliarie.
Tabella comparativa
| Algoritmo | Migliore | Medio | Peggiore | Memoria ausiliaria | Stabile | In place |
|---|---|---|---|---|---|---|
| Insertion sort | Θ(n) | Θ(n²) | Θ(n²) | Θ(1) | Sì | Sì |
| Merge sort | Θ(n log n) | Θ(n log n) | Θ(n log n) | Θ(n) | Sì | No |
| Quicksort | Θ(n log n) | Θ(n log n) | Θ(n²) | Θ(log n)¹ | No | Sì |
| Heapsort | Θ(n log n) | Θ(n log n) | Θ(n log n) | Θ(1) | No | Sì |
| Counting sort | Θ(n + k) | Θ(n + k) | Θ(n + k) | Θ(n + k) | Sì | No |
| Radix sort (LSD) | Θ(d(n + b)) | Θ(d(n + b)) | Θ(d(n + b)) | Θ(n + b) | Sì | No |
| Bucket sort | Θ(n + k) | Θ(n + k)² | Θ(n²) | Θ(n + k) | Dipende³ | No |
1 Stack medio di quicksort; nel caso peggiore può diventare Θ(n). “In place” qui ammette lo stack ricorsivo.
2 Con distribuzione circa uniforme nei k secchi e ordinamento locale appropriato.
3 Bucket sort è stabile soltanto se distribuzione, ordinamento interno e concatenazione preservano l’ordine delle chiavi uguali.
Parametri: n elementi; k ampiezza dell’intervallo o numero di secchi; d cifre; b base numerica.
Due famiglie, due limiti diversi
Ordinamenti non comparativi
Counting, radix e bucket sort sfruttano la struttura delle chiavi. Possono essere lineari in n, ma il costo dipende anche da intervallo, cifre o distribuzione.
Apri un simulatore
Θ(n²)
Insertion sort
Inserisce ogni elemento nella parte già ordinata.
Studia e simula →Θ(n log n)
Merge sort
Divide, ordina le metà e le fonde.
Studia e simula →Θ(n log n)
Quicksort
Partiziona gli elementi attorno a un pivot.
Studia e simula →Θ(n log n)
Heapsort
Costruisce un max-heap ed estrae il massimo.
Studia e simula →Θ(n + k)
Counting sort
Conta le occorrenze di ogni chiave intera.
Studia e simula →Θ(d(n + b))
Radix sort (LSD)
Ordina una cifra alla volta con passaggi stabili.
Studia e simula →Θ(n + k)²
Bucket sort
Distribuisce i valori in intervalli e ordina i secchi.
Studia e simula →Come scegliere in pratica
Nelle librerie reali si usano spesso algoritmi ibridi: insertion sort per sottoproblemi piccoli, introsort per limitare il caso peggiore di quicksort, o Timsort per sfruttare sequenze già ordinate.
Le proprietà che la sola complessità non racconta
- Stabile
- Elementi con la stessa chiave mantengono il loro ordine relativo. È essenziale negli ordinamenti successivi per più campi.
- In place
- Usa una quantità costante o molto piccola di memoria oltre all’array; le convenzioni sullo stack ricorsivo vanno esplicitate.
- Adattivo
- Diventa più veloce quando l’input è già parzialmente ordinato. Insertion sort ne è l’esempio classico.
- Online
- Può mantenere l’ordine mentre arrivano nuovi elementi. Insertion sort si presta naturalmente.