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