10.1 Confronto di vari algoritmi di ordinamento
Questa è una tabella comparativa per diversi algoritmi di ordinamento:
| Algoritmo | Miglior tempo | Tempo medio | Peggior tempo | Complessità spaziale | Stabilità |
|---|---|---|---|---|---|
| Ordinamento a bolle (Bubble Sort) | O(n) | O(n^2) | O(n^2) | O(1) | Sì |
| Ordinamento per inserzione (Insertion Sort) | O(n) | O(n^2) | O(n^2) | O(1) | Sì |
| Ordinamento per selezione (Selection Sort) | O(n^2) | O(n^2) | O(n^2) | O(1) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Sì |
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
10.2 Criteri per scegliere un algoritmo di ordinamento per diverse attività
Ogni algoritmo ha i suoi punti di forza e di debolezza. Su piccole quantità di dati, anche l'ordinamento a bolle può essere la scelta migliore.
Dovresti considerare i seguenti criteri:
1. Dimensione dei dati:
- Piccoli insiemi di dati (n < 1000):
- Ordinamento a bolle, Ordinamento per inserzione: semplici e comprensibili, efficaci per piccoli insiemi di dati.
- Grandi insiemi di dati (n > 1000):
- Merge Sort, Quick Sort, Heap Sort: più complessi, ma efficaci per grandi volumi di dati.
2. Struttura dei dati:
- Dati quasi ordinati:
- Ordinamento per inserzione: funziona quasi linearmente per dati quasi ordinati.
- Dati casuali:
- Quick Sort, Merge Sort, Heap Sort: efficaci per dati casuali.
3. Stabilità:
- Se è richiesta la stabilità:
- Ordinamento per inserzione, Merge Sort: mantengono l'ordine relativo degli elementi con gli stessi valori.
- Se non è richiesta la stabilità:
- Ordinamento per selezione, Quick Sort, Heap Sort: possono essere usati se la stabilità non è importante.
4. Memoria addizionale:
- Memoria limitata:
- Ordinamento per inserzione, Ordinamento per selezione, Heap Sort: utilizzano
O(1)memoria addizionale.
- Ordinamento per inserzione, Ordinamento per selezione, Heap Sort: utilizzano
- Memoria addizionale disponibile:
- Merge Sort: richiede
O(n)memoria addizionale, ma può essere efficace per grandi quantità di dati.
- Merge Sort: richiede
10.3 Esempi di problemi in cui un algoritmo è preferibile rispetto a un altro
Ora consideriamo i problemi invece degli algoritmi. Esempi di problemi in cui un algoritmo è preferibile rispetto a un altro:
1. Ordinamento di piccole matrici:
Ordinamento a bolle, Ordinamento per inserzione: la semplicità di implementazione li rende ideali per piccole matrici, soprattutto se le matrici sono quasi ordinate.
2. Ordinamento di grandi matrici:
Quick Sort, Merge Sort, Heap Sort: efficaci per grandi volumi di dati grazie alla loro complessità temporale logaritmica.
3. Ordinamento di matrici quasi ordinate:
Ad esempio, hai inserito alcuni elementi in una matrice già ordinata.
Ordinamento per inserzione: lavora quasi linearmente su tali matrici.
4. Ordinamento di dati dove è importante la stabilità:
Merge Sort: mantiene l'ordine degli elementi identici ed è efficace per grandi volumi di dati.
Ordinamento per inserzione: mantiene anche l'ordine ed è efficace per piccoli volumi di dati.
5. Ordinamento con memoria limitata:
Ordinamento per selezione, Heap Sort: utilizzano solo O(1) memoria addizionale e possono essere usati quando la memoria è limitata.
6. Ordinamento parallelo:
Merge Sort: si paralizza facilmente, poiché ogni metà può essere ordinata indipendentemente.
GO TO FULL VERSION