W dniu poniedziałek, 15 października 2012 00:01:17 UTC+2 użytkownik bartekltg
napisał:
> W dniu 2012-10-14 23:43, kenobi pisze:
>
>
>
> >>
>
> > histogramy maka tu po 256KB wiec o jakich 40MB mowa,
>
>
>
> Na tablice pomocniczą.
>
>
>
> unsigned int * temp = new unsigned int [n];
>
>
>
> Sortowanie pozycyjne wymaga n dodatkowej pamięci.
>
>
>
> a n było 10 000 000
>
>
>
> > jest to poniekad przypuszczam algorytm najszybszy
>
> > z wszystkich omawianych :U
>
>
>
> Ale nie jest to algorytm uniwersalny.
>
>
>
>
>
> A, jednak istnieją wersje sortowania pozycyjnego
>
> dziające się w odwrotnej kolejności.
>
> Ale nadal dziwnie przypominają kubełkowe.
>
>
>
>
>
wyniki moich pomiarow w stosunku do qsorta z clib

//tab_size qsort komb-hist

//100 20 u 800 u
//1 tys 250 u 1000 u
//10 tys 3.3 m 1.2 m
//100 tys 40 m 20 m
//1 mln 600 m 350 m
//10 mln 6.2 s 3.9 s

niecale 2 razy szybsze :/ no ale to jest
wersja kombinowana, oryginalna na podstawowym
zakresie (ktory nie jest taki maly do miliona
uciagnie itp) pewnie bylaby ze 4 razy szybsza
wiec ogolnie z 10 razy szybsza od quicksorta