Avaliação Experimental (ordenação)
From Wiki**3
Algortimos Elementares
N Selection Insertion Bubble
1000 5 4 11
2000 21 15 45
4000 85 62 182
Shell Sort
Avaliação experimental em função da sequência h. Note-se o mau desempenho da sequência baseada em potências de 2.
N O K G S P I 12500 16 6 6 5 6 6 25000 37 13 11 12 15 10 50000 102 31 30 27 38 26 100000 303 77 60 63 81 58 200000 817 178 137 139 180 126
Valores das sequências de h:
O: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, ... K: 1, 4, 13, 40, 121, 364, ... G: 1, 2, 4, 10, 23, 51, 113, 249, 548, ... S: 1, 8, 23, 77, 281, ... P: 1, 7, 8, 49, 56, 64, 343, 392, 448, 512, ... I: 1, 5, 19, 41, 109, 209, 505, 929, ...
Quicksort vs. Heapsort
N Quick Heap H/Q%
12500 2 3 150
25000 7 8 114
50000 13 18 138
100000 27 42 156
200000 58 100 172
400000 122 232 190
800000 261 542 208
Quicksort vs. Mergesort
top-down bottom-up
N Q T T* O B B*
12500 2 5 4 4 5 4
25000 5 12 8 8 11 9
50000 11 23 20 17 26 23
100000 24 53 43 37 59 53
200000 52 111 92 78 127 110
400000 109 237 198 168 267 232
800000 241 524 426 358 568 496
Q: quicksort
T: top-down mergesort; T*: T+cutoff; O: T+cutoff+nocopy
B: bottom-up mergesort; B*: B+cutoff
Quicksort vs. Radix Sort
N Q MSD LSD
12500 2 28 4
25000 5 29 8
50000 10 35 18
100000 21 47 39
200000 49 72 81
400000 102 581 169
800000 223 6064 328