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