Avaliação Experimental (ordenação)

From Wiki**3

Revision as of 17:10, 27 May 2005 by Root (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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