In questa sezione compariamo insertion sort, shell
sort e quicksort. Ci sono molti fattori che influenzano la scelta di un
algoritmo di ordinamento:
-
Stable sort. Ricorda
che un stable sort lascerà identici elementi nella stessa posizione
nell'output ordinato. Insertion sort è
stable.
-
Space. Un in-place
sort non richiede nessuno spazio extra per compiere il compito. Sia insertion
sort che shell sort sono in-place sorts. Quicksort
richiede uno spazio di stack per la recursione, e perciò è
un non in-place sort. Armeggiando con l'algoritmo riduce considerevolmente
la quantità di tempo richiesto.
-
Tempo. Il tempo
richiesto per ordinare un insieme di dati può facilmente diventare
astronomico (Tavola 1). La Tavola
2 mostra la tempestività per ogni metodo. Il tempo richiesto
per ordinare un insieme di dati disordinati è mostrato in Tavola
3.
-
Semplicità. Il numero di statements
(blocchi di comandi) richiesti per ogni algoritmo può essere trovato
in Tavola 2. Gli algoritmi semplici favoriranno
un minor numero di errori.
Tavola 1
n |
log n |
nlogn |
n^1.25 |
n^2 |
1 |
0 |
0 |
1 |
1 |
16 |
4 |
64 |
32 |
256 |
256 |
8 |
2.048 |
1.024 |
65.536 |
4.096 |
12 |
49.152 |
32.768 |
16.777.216 |
65.536 |
16 |
1.048.565 |
1.048.476 |
4.294.967.296 |
1.048.476 |
20 |
20.969.520 |
33.554.432 |
1.099.301.922.576 |
16.755.616 |
24 |
402.614.784 |
1.073613.825 |
281.421.292.179.456 |
TAVOLA 1. Tasso di crescita per
varie funzioni
Tavola 2
metodo |
statements |
complessità media |
complessità caso pessimo |
insertion sort |
9 |
O(n^2) |
O(n^2) |
shell sort |
17 |
O(n^1.25) |
O(n^1.5) |
quicksort |
21 |
O(nlogn) |
O(n^2) |
TAVOLA 2. Comparazione dei metodi
Tavola 3
conteggi |
insertion |
shell |
quicksort |
16 |
39 ms |
45 ms |
51 ms |
256 |
4.969 ms |
1.230 ms |
911 ms |
4.096 |
1.315 sec |
0.033 sec |
0.020 sec |
65.536 |
416.437 sec |
1.254 sec |
0.461 sec |
TABELLA 3. Tempestività degli
algortimi di sort
Troverai un'ulteriore comparazione, tra bubblesort e quicksort, qui.
