ordenacao -s1234567 -r -q (10 sequencias aleatorias)
n shell merge_r merge_i heap quick quickCLR qsort
256 0.00 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 0.00
1024 0.00 0.00 0.00 0.00 0.00 0.00 0.00
2048 0.00 0.01 0.00 0.00 0.00 0.00 0.01
4096 0.01 0.01 0.00 0.01 0.00 0.00 0.01
8192 0.01 0.01 0.01 0.01 0.01 0.01 0.03
16384 0.03 0.02 0.02 0.02 0.02 0.02 0.06
32768 0.07 0.05 0.05 0.04 0.04 0.04 0.12
65536 0.16 0.11 0.11 0.10 0.07 0.08 0.25
131072 0.38 0.25 0.33 0.23 0.16 0.16 0.54
262144 0.92 0.54 0.73 0.54 0.34 0.35 1.15
524288 2.13 1.18 1.55 1.31 0.74 0.77 2.44
1048576 4.97 2.52 3.32 3.06 1.60 1.65 5.20
2097152 11.38 5.42 6.96 7.07 3.38 3.48 10.88
4194304 26.50 11.40 14.46 15.84 7.16 7.40 22.78
8388608 61.68 24.35 29.76 35.85 15.24 15.66 47.85
ordenacao -d -r -q (ordem decrescente)
n shell merge_r merge_i heap quick quickCLR qsort
256 0.00 0.00 0.00 0.00 0.00 0.00 0.00
512 0.00 0.00 0.01 0.00 0.00 0.00 0.00
1024 0.00 0.00 0.00 0.01 0.00 0.01 0.00
2048 0.01 0.00 0.00 0.00 0.06 0.02 0.01
4096 0.00 0.01 0.00 0.00 0.22 0.11 0.01
8192 0.00 0.01 0.01 0.01 0.90 0.49 0.02
16384 0.02 0.02 0.02 0.01 3.70 2.24 0.04
32768 0.03 0.04 0.04 0.03 15.29 9.74 0.08
65536 0.07 0.09 0.09 0.07 62.23 41.33 0.18
131072 0.15 0.21 0.28 0.16 261.26 180.26 0.40
ordenacao -c -r -q (ordem crescente)
n shell merge_r merge_i heap quick quickCLR qsort
256 0.00 0.00 0.00 0.00 0.00 0.00 0.00
512 0.01 0.00 0.00 0.00 0.00 0.00 0.00
1024 0.00 0.01 0.00 0.00 0.02 0.00 0.00
2048 0.01 0.00 0.00 0.00 0.07 0.03 0.00
4096 0.01 0.00 0.01 0.00 0.29 0.12 0.00
8192 0.00 0.01 0.01 0.01 1.16 0.53 0.02
16384 0.01 0.02 0.02 0.01 4.63 2.28 0.03
32768 0.02 0.05 0.04 0.03 18.47 9.21 0.06
65536 0.05 0.10 0.10 0.07 74.16 37.89 0.11
131072 0.12 0.23 0.28 0.16 372.45 232.66 0.23
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
qsort = quicksort da biblioteca C
compilador: gcc -O2
computador: Pentium II, 233Mhz, 128Mbytes