-
Data: 2012-10-14 22:57:21
Temat: Re: sortowanie
Od: kenobi <p...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]W dniu niedziela, 14 października 2012 22:51:46 UTC+2 użytkownik kenobi napisał:
> 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?
w kazdym razie jesli to nie ma bledu i dziala
to jest to sprytny kawalek kodu - dziwne jednak jakoby to mialo byc tylko 2-3 razy
szybsze, new
mona wyrzucic i zrobic histogramy na statycznych tablicach
Następne wpisy z tego wątku
- 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
- 15.10.12 17:19 bartekltg
- 15.10.12 17:34 kenobi
- 15.10.12 17:40 kenobi
Najnowsze wątki z tej grupy
- Alg. kompresji LZW
- Popr. 14. Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- 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??
Najnowsze wątki
- 2025-02-17 Kraków => MS Dynamics 365BC/NAV Developer <=
- 2025-02-17 Chrzanów => Programista NodeJS <=
- 2025-02-17 Warszawa => Node.js / Fullstack Developer <=
- 2025-02-17 Białystok => System Architect (Java background) <=
- 2025-02-17 Białystok => Solution Architect (Java background) <=
- 2025-02-17 Gliwice => Team Lead / Tribe Lead FrontEnd <=
- 2025-02-17 Gdańsk => PHP Developer <=
- 2025-02-17 Warszawa => Senior ASP.NET Developer <=
- 2025-02-17 Gliwice => Business Development Manager - Network and Network Security
- 2025-02-17 Mińsk Mazowiecki => Area Sales Manager OZE <=
- 2025-02-17 Odśnieżanie samochodu
- 2025-02-17 Katowice => Regionalny Kierownik Sprzedaży (OZE) <=
- 2025-02-17 Dęblin => JavaScript / Node / Fullstack Developer <=
- 2025-02-17 Pompiarze...
- 2025-02-16 PV teraz