-
Data: 2012-10-14 22:19:00
Temat: Re: sortowanie
Od: bartekltg <b...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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
Następne wpisy z tego wątku
- 14.10.12 22:42 kenobi
- 14.10.12 22:51 kenobi
- 14.10.12 22:57 kenobi
- 14.10.12 23:27 bartekltg
- 14.10.12 23:43 kenobi
- 15.10.12 00:01 bartekltg
- 15.10.12 00:43 kenobi
- 15.10.12 00:54 bartekltg
- 15.10.12 01:39 M.M.
- 15.10.12 07:49 kenobi
- 15.10.12 08:00 kenobi
- 15.10.12 08:53 Tomasz Kaczanowski
- 15.10.12 10:03 kenobi
- 15.10.12 13:25 kenobi
- 15.10.12 16:41 bartekltg
Najnowsze wątki z tej grupy
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
Najnowsze wątki
- 2025-01-04 Zbieranie danych przez www
- 2025-01-04 reverse engineering i dodawanie elementów do istniejących zamkniętych produktów- legalne?
- 2025-01-04 w Nowym Roku 2025r
- 2025-01-04 Warszawa => Specjalista ds. IT - II Linia Wsparcia <=
- 2025-01-04 Warszawa => Java Developer <=
- 2025-01-04 Warszawa => Spedytor Międzynarodowy <=
- 2025-01-04 Warszawa => System Architect (Java background) <=
- 2025-01-04 Wrocław => Application Security Engineer <=
- 2025-01-04 Chrzanów => Specjalista ds. public relations <=
- 2025-01-04 Katowice => Key Account Manager (ERP) <=
- 2025-01-03 Problem z odczytem karty CF
- 2025-01-03 Jazda z Warszawy do Krakowa teslą
- 2025-01-03 Wrocław => Konsultant Wdrożeniowy Comarch XL/Optima (Księgowość i
- 2025-01-03 Warszawa => International Freight Forwarder <=
- 2025-01-03 Mińsk Mazowiecki => Area Sales Manager OZE <=