View source for Avaliação Experimental (ordenação)

== 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