W dniu niedziela, 14 października 2012 12:57:53 UTC+2 użytkownik kenobi napisał:
> W dniu niedziela, 14 października 2012 12:50:00 UTC+2 użytkownik bartekltg napisał:
>
> > W dniu 2012-10-14 12:06, kenobi pisze:
>
> >
>
> >
>
> >
>
> >
>
> >
>
> > > w pierwszym przejsciu liczysz histogram, czyli
>
> >
>
> > > 256 offsetow, w drugim wstawiasz wzgledem tych
>
> >
>
> > > ofsetow i masz zgrubnie posortowane, reszte
>
> >
>
> > > podobnie lub ew merge sortem bedzie potezny
>
> >
>
> > > speedup ;)
>
> >
>
> >
>
> >
>
> >
>
> >
>
> > Całą idea i "prawdziwy speedup" wynika stąd,
>
> >
>
> > że surtujemy _w odwrotnej kolejności_ algorytmem
>
> >
>
> > stabilnym. najpierw posortujemy po niższym
>
> >
>
> > bajcie. Ok. Teraz sortujemy po wyższym.
>
> >
>
> > Jeśli jakieś dwie liczby mają taki sam bajt wyższy,
>
> >
>
> > to nie zostanie zamieniona ich kolejność.
>
> >
>
> > A, że był wcześniej posortowane po niższym,
>
> >
>
> > to są posortowane po obydwu słownikowo.
>
> >
>
> > koniec.
>
> >
>
> >
>
> >
>
> > żadnych dodatkowych kontenerów, żadnych histogramów,
>
> >
>
> > żadnego mergesorta nie wiadomo skąd.
>
> >
>
> > Tylko dodatkowa tablica (stabilne sortowanie przez
>
> >
>
> > zliczanie nie działą w miejscu) i wydajność;)
>
> >
>
> >
>
>
>
> ok zastanowie sie, mozliwe (musze przemyslec chwile) - jesli tak to fajnie bo mozna

>
> latwo uogolnic kasperskiego
>
> - w kazdym razie widzisz pewnie ze kasperski/histogram jest to najszybsza metoda ;>

chwile sie zastonowilem i bez modyfikacji nie
da sie trzeba jednak zmodyfikowac in przerzucic histogram na offsety by zliczyc
miejsce na listy,