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;

}

pzdr
bartekltg