ordenacao -r -s1234567 (10 sequencias aleatorias)
n shell merge_r merge_i heap quick quickCLR
256 0.00 0.00 0.00 0.00 0.00 0.00
512 0.00 0.00 0.00 0.00 0.00 0.00
1024 0.00 0.00 0.00 0.00 0.00 0.00
2048 0.00 0.00 0.00 0.00 0.00 0.00
4096 0.01 0.01 0.00 0.01 0.00 0.00
8192 0.01 0.01 0.01 0.01 0.01 0.01
16384 0.03 0.02 0.02 0.02 0.02 0.02
32768 0.07 0.05 0.05 0.04 0.04 0.04
65536 0.17 0.11 0.12 0.10 0.07 0.08
131072 0.40 0.25 0.32 0.23 0.16 0.17
262144 0.93 0.54 0.65 0.55 0.34 0.36
524288 2.14 1.15 1.41 1.31 0.75 0.77
1048576 4.99 2.49 3.00 3.08 1.60 1.66
2097152 11.48 5.32 6.41 7.12 3.40 3.51
8388608 61.72 23.60 27.91 35.72 15.24 15.68
ordenacao -r -c (sequencia em ordem crescente)
n shell merge_r merge_i heap quick quickCLR
256 0.00 0.00 0.00 0.00 0.00 0.00
512 0.00 0.00 0.00 0.01 0.00 0.00
1024 0.00 0.00 0.00 0.00 0.02 0.01
2048 0.00 0.00 0.01 0.00 0.07 0.03
4096 0.00 0.01 0.00 0.00 0.32 0.11
8192 0.00 0.01 0.01 0.01 1.16 0.54
16384 0.01 0.02 0.01 0.02 4.63 2.28
32768 0.02 0.04 0.04 0.04 18.95 9.81
65536 0.05 0.10 0.10 0.07 79.02 42.79
131072 0.12 0.21 0.25 0.16 361.20 223.90
Legenda:
shell = shellsort original (Knuth)
merge_r = mergesort recursivo (top-down)
merge_i = mergesort iterativo (bottom-up)
heap = heapsort
quick = quicksort recursivo com o algoritmo de separacao das notas
de aula do professor Paulo Feofiloff
quickCLR = quicksort recursivo do livro do Cormen, Leiserson e Rivest
compilador: gcc -O2
computador: Pentium II, 233Mhz, 128Mbytes