W dniu 2012-10-14 12:42, bartekltg pisze:

> O, znalazłem ciekawą stronę.
> http://pages.ripco.net/~jgamble/nw.html
>
> http://jgamble.ripco.net/cgi-bin/nw.cgi?inputs=5&alg
orithm=batcher&output=svg

>
> Mógłbyś użyć takiego ciągu (uwaga, zrobione automatycznie
> z wyników podanych przez stronę). daj znać, czy przebija sort10;)


Napisałem skrypcik, który ściągnął 'Best' i 'Batcher's Merge-Exchange',
wybrał ten z mniejszą liczbą porównań i przerobił na c++.

Wyniki: [na dole]

Jest to szybsze od klasycznych alg aż do 11 elementów.
Potem gwałtownie zwalnia.
Nie do końca odpowiada to skokom liczby porównań
(35 do 39). Pewnie program robi się 'za duży'.

A, kod: http://pastebin.com/qmzqfiHK
:D

pzdr
bartekltg


Czasy, [n, powtorzen, T_insert, T_select, T_sieciowy]
2, 24999999, 196.000000, 284.000000 210.000000 ;
3, 11111110, 179.000000, 223.000000 153.000000 ;
4, 6249999, 157.000000, 192.000000 134.000000 ;
5, 3999999, 142.000000, 180.000000 116.000000 ;
6, 2777777, 140.000000, 184.000000 105.000000 ;
7, 2040816, 130.000000, 191.000000 99.000000 ;
8, 1562499, 120.000000, 197.000000 94.000000 ;
9, 1234567, 110.000000, 198.000000 94.000000 ;
10, 999999, 102.000000, 195.000000 86.000000 ;
11, 826446, 95.000000, 190.000000 82.000000 ;
12, 694444, 89.000000, 183.000000 168.000000 ;
13, 591715, 85.000000, 178.000000 183.000000 ;
14, 510204, 80.000000, 174.000000 171.000000 ;
15, 444444, 77.000000, 170.000000 164.000000 ;
16, 390624, 73.000000, 165.000000 153.000000 ;
17, 346020, 70.000000, 161.000000 174.000000 ;
18, 308641, 67.000000, 157.000000 172.000000 ;
19, 277008, 65.000000, 155.000000 172.000000 ;
20, 249999, 63.000000, 151.000000 165.000000 ;
22, 206611, 59.000000, 146.000000 159.000000 ;
24, 173611, 57.000000, 140.000000 148.000000 ;
26, 147928, 54.000000, 136.000000 145.000000 ;
28, 127550, 52.000000, 132.000000 138.000000 ;
30, 111111, 50.000000, 129.000000 132.000000 ;
32, 97656, 48.000000, 126.000000 124.000000 ;