W dniu 2012-11-24 16:25, PK pisze:
> On 2012-11-24, bartekltg <b...@g...com> wrote:
>> Niedawno był to całkiem niezły watek o sortowaniu.
>> Sortowania pozycyjne tez były omówione;)
>
> Wiem. W nim również zwróciłem slawkowi uwagę, że nie rozumie sortowania,
> a potem przestałem się udzielać, bo po prostu żal mi było czasu. Nie
> mniej widzę, że Wasza dyskusja (trwająca chyba kilka tygodni) była
> dla niego zupełnie bezowocna.

Hmm, dyskusja była chyba głownie w około fira.
Zresztą, nie pamiętam dokładnie.


>> Ale posortować beż użycia > na elementach sortowanych się da;)
>> Pewnych specyficznych elementów, jak liczby naturalne.
>
> Można zastąpić relację ">" obliczeniem pewnych f(a,b) i g(a,b), ale
> wyniki tych funkcji trzeba przyrównać do zera.
> Poza tym operacja "=" jest zazwyczaj wolniejsza niż ">".

Ale czasem złożonością jednak przebija. Posortowanie
miliarda bajtów będzie szybsze 'sortowaniem przez zliczanie'
niz qsortem. Tylko jak często mamy taką potrzebę;-)


Odkopałem test, który robiłem w tamtej dyskusji.
Wygląda, że i inty lecą szybciej. Pod warunkiem,
że tablica jest dostatecznie duża.

A, to nizej to kod chyba niepoprawiony, sortowanie
nie jest stabilne. Trzeba gdzieś zamienić kierunek pętli.

pzdr
bartekltg


***
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