W dniu niedziela, 14 października 2012 22:19:08 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-10-14 20:01, bartekltg pisze:
>
> >> w tym drugim wypadku (z intami) - jak dokladnie?
>
> >
>
> > Najpierw dla 2 niższych bajtów, potem dla 2 wyzszych.
>
> > Tablica pomocnicza tylko jedna, raz z oryginału lecimy
>
> > na pomocniczą, drugim razem z powrotem.
>
> >
>
> >> (kod w c) bo to jest druga czesc tego o czym ja tu pisze
>
> >
>
> > Mam Ci kod napisać? A za ile;>
>
>
>
>
>
> Niech będzie dzień dobroci.
>
> Przetestowane, porównane z std::sort
>
> Na przedziale n 10^5 - 10^7 przewaga 2 do 3.5 raza
>
> szybsze. Co ciekawe, przewaga pozycyjnego od pewnego
>
> momentu maleje.
>
>
>
>
>
> void pozycyjne(unsigned int * tab, int n)
>
> {
>
> const int shift = 16;
>
> const int K = 1<<shift;
>
>
>
> int * h = new int [K];
>
> unsigned int * temp = new unsigned int [n];
>
>
>
>
>
> for (int j=0;j<K;j++) //zerowanie
>
> h[j]=0;
>
>
>
> for (int j=0;j<n;j++)//zliczanie wystąpień
>
> h[(unsigned short)(tab[j])]++;
>
>
>
> for (int j=1;j<K;j++) //akumulacja/zmiana liczby wystąpień
>
> h[j]+=h[j-1]; //na indeksy
>
>
>
> for (int j=0;j<n;j++)//kopiowanie
>
> {
>
> temp[--h[(unsigned short)tab[j]]]=tab[j];
>
> }
>
> ///////////faza druga
>
> for (int j=0;j<K;j++) //zerowanie
>
> h[j]=0;
>
>
>
> for (int j=0;j<n;j++)//zliczanie wystąpień
>
> h[(unsigned short)(temp[j]>>shift)]++;
>
>
>
> for (int j=1;j<K;j++) //akumulacja/zmiana liczby wystąpień
>
> h[j]+=h[j-1]; //na indeksy
>
>
>
> for (int j=n-1;j>=0;j--)//kopiowanie
>
> {
>
> tab[--h[(unsigned short)temp[j]>>shift]]=temp[j];
>
> }
>
>
>
> delete[]temp;
>
> delete[]h;
>
>
>
> }
>
>
nie rozumiem tego zlozenia, jak sortowanie tego
co bylo posortowane po niskiej polowie po wysokiej czesci zlozy sie tak by wszystko
bylo ok?