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.
