-
Data: 2012-10-14 22:51:46
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: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?
Następne wpisy z tego wątku
- 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
- 15.10.12 17:19 bartekltg
- 15.10.12 17:34 kenobi
Najnowsze wątki z tej grupy
- Grok zaczął nadużywać wulgaryzmów i wprost obrażać niektóre znane osoby
- Can you activate BMW 48V 10Ah Li-Ion battery, connecting to CAN-USB laptop interface ?
- We Wrocławiu ruszyła Odra 5, pierwszy w Polsce komputer kwantowy z nadprzewodzącymi kubitami
- Ada-Europe - AEiC 2025 early registration deadline imminent
- John Carmack twierdzi, że gdyby gry były optymalizowane, to wystarczyły by stare kompy
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2025
- Linuks od wer. 6.15 przestanie wspierać procesory 486 i będzie wymagać min. Pentium
- ,,Polski przemysł jest w stanie agonalnym" - podkreślił dobitnie, wskazując na brak zamówień.
- Rewolucja w debugowaniu!!! SI analizuje zrzuty pamięci systemu M$ Windows!!!
- Brednie w wiki - hasło Dehomag
- Perfidne ataki krakerów z KRLD na skrypciarzy JS i Pajton
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- U nas propagują modę na SI, a w Chinach naukowcy SI po kolei umierają w wieku 40-50lat
Najnowsze wątki
- 2025-07-25 Drastycznie rośnie import stali - w hucie w Dąbrowie Górniczej zostanie wygaszony wielki piec
- 2025-07-25 Drastycznie rośnie import stali - w hucie w Dąbrowie Górniczej zostanie wygaszony wielki piec
- 2025-07-25 I kolejny inżynier...
- 2025-07-25 Kobiety, bójcie się inżynierów...
- 2025-07-25 Warszawa => Konsultant Wiodący SAP PP <=
- 2025-07-25 Re: Brawo !!! Osy chronione w Niemczech. Za usunięcie gniazda grozi mandat
- 2025-07-25 cudzoziemiec bez biletu
- 2025-07-25 Gdynia => Sales Executive / KAM <=
- 2025-07-25 Inżynierzy z prawomocnym...
- 2025-07-25 Łódź => Mainframe (z/OS, Assembler) Developer <=
- 2025-07-25 Warszawa => Inżynier oprogramowania .Net <=
- 2025-07-25 Kraków => Senior Fullstack Engineer (Low-Code Platform) <=
- 2025-07-25 Skrobanie
- 2025-07-25 Lublin => Konsultant ds. Wdrożeń ERP (moduł FK) <=
- 2025-07-25 Warszawa => Senior Frontend Developer (React + React Native) <=