>
> :) nie rozumiem, sorry.
>
>

masz tablice tab[]

robisz przebiieg po tablicy forem, od
poczatku do konca for(int i=0; i<tab_size; i++)

jesli napotkasz elemant mniejszy od wartosci C to swapujesz go do lewej, na poczatek,

poczatek na poczatku wynosi 0 ale za kazdym
dorzuconym robisz poczatek++ bo chodzi o to
zeby te swapnieta na lewo zostawic w spokoju


int poczatek = 0;

for(int i=0; i<tab_max; i++)
{
if( tab[i] < C )
{
swap_tab(i,poczatek);
p++;
}

}

po prostu robisz przebieg po tab[i]
i wszystkie wartosci tab[i] < C swapujesz
na lewo a wieksze na prawo -

to jest szybkie bo jeden jedyny przebieg
odwala juz cala mase swapow

do góry

oczywiscie i tak jest to slamazarstwo
najlepsze sortowanie to to co ja nazywam
metoda chrissa kaserskiego, czyli

h[ tab[i] ]++;

Podobno kiedys zrobil tak na jakiejs
olimpiadzie jako nastolatek i komisja
mu tego nie uznala ;-) zarabista anegdota
(pisalem o tym z rok czy dwa temu)

Mozna to uogolnic np w h(tab[i])
robiac galaz drzewa, albo innymi metodami
i mysle ze to raczej jest po prostu najszybsze

do góry

Dnia Sat, 13 Oct 2012 10:21:50 -0700, kenobi napisal:

>>
>> :) nie rozumiem, sorry.
>>
>>
>
> masz tablice tab[]
>
> robisz przebiieg po tablicy forem, od
> poczatku do konca for(int i=0; i<tab_size; i++)
>
> jesli napotkasz elemant mniejszy od wartosci C to swapujesz go do lewej, na
poczatek,
>
> poczatek na poczatku wynosi 0 ale za kazdym
> dorzuconym robisz poczatek++ bo chodzi o to
> zeby te swapnieta na lewo zostawic w spokoju
>
>
> int poczatek = 0;
>
> for(int i=0; i<tab_max; i++)
> {
> if( tab[i] < C )
> {
> swap_tab(i,poczatek);
> p++;
> }
>
> }
>
> po prostu robisz przebieg po tab[i]
> i wszystkie wartosci tab[i] < C swapujesz
> na lewo a wieksze na prawo -
>
> to jest szybkie bo jeden jedyny przebieg
> odwala juz cala mase swapow

No to już brzmi fajnie. A co to było to C, która wartość to ma być?
Poza tym, czy swapów nie miało być jak najmniej?

--
Edek

do góry

W dniu sobota, 13 października 2012 19:39:51 UTC+2 użytkownik Edek Pienkowski
napisał:
> Dnia Sat, 13 Oct 2012 10:21:50 -0700, kenobi napisal:
>
>
>
> >>
>
> >> :) nie rozumiem, sorry.
>
> >>
>
> >>
>
> >
>
> > masz tablice tab[]
>
> >
>
> > robisz przebiieg po tablicy forem, od
>
> > poczatku do konca for(int i=0; i<tab_size; i++)
>
> >
>
> > jesli napotkasz elemant mniejszy od wartosci C to swapujesz go do lewej, na
poczatek,
>
> >
>
> > poczatek na poczatku wynosi 0 ale za kazdym
>
> > dorzuconym robisz poczatek++ bo chodzi o to
>
> > zeby te swapnieta na lewo zostawic w spokoju
>
> >
>
> >
>
> > int poczatek = 0;
>
> >
>
> > for(int i=0; i<tab_max; i++)
>
> > {
>
> > if( tab[i] < C )
>
> > {
>
> > swap_tab(i,poczatek);
>
> > p++;
>
> > }
>
> >
>
> > }
>
> >
>
> > po prostu robisz przebieg po tab[i]
>
> > i wszystkie wartosci tab[i] < C swapujesz
>
> > na lewo a wieksze na prawo -
>
> >
>
> > to jest szybkie bo jeden jedyny przebieg
>
> > odwala juz cala mase swapow
>
>
>
> No to już brzmi fajnie. A co to było to C, która wartość to ma być?
>
> Poza tym, czy swapów nie miało być jak najmniej?
>

C to dowolna wartosc z tablicy najlepiej gdyby to byla taka ktora podzieli tablice na
dwa zblizone wielkoscia kawalki, mozna wylosowac
dowolna np ze srodka przedzialu, wazne tylko
by nie miec wielkiego pecha w wielce dlugiej serii - bo wtedy stos sie wywali - ale
taki pech jest malo prawdopodobny

do góry

Dnia Sat, 13 Oct 2012 10:50:01 -0700, kenobi napisal:

>>
>> No to już brzmi fajnie. A co to było to C, która wartość to ma być?
>>
>> Poza tym, czy swapów nie miało być jak najmniej?
>>
>>
> C to dowolna wartosc z tablicy najlepiej gdyby to byla taka ktora podzieli
> tablice na dwa zblizone wielkoscia kawalki, mozna wylosowac dowolna np ze
> srodka przedzialu, wazne tylko by nie miec wielkiego pecha w wielce
> dlugiej serii - bo wtedy stos sie wywali - ale taki pech jest malo
> prawdopodobny

Dowolna, czy się ją jakoś wybiera? Nie można robiąc te swapy na lewo
i prawo policzyć sobie średniej przy okazji?

--
Edek

do góry

W dniu sobota, 13 października 2012 20:01:01 UTC+2 użytkownik Edek Pienkowski
napisał:
> Dnia Sat, 13 Oct 2012 10:50:01 -0700, kenobi napisal:
>
>
>
> >>
>
> >> No to ju� brzmi fajnie. A co to by�o to C, kt�ra warto�� to ma by�?
>
> >>
>
> >> Poza tym, czy swap�w nie mia�o by� jak najmniej?
>
> >>
>
> >>
>
> > C to dowolna wartosc z tablicy najlepiej gdyby to byla taka ktora podzieli
>
> > tablice na dwa zblizone wielkoscia kawalki, mozna wylosowac dowolna np ze
>
> > srodka przedzialu, wazne tylko by nie miec wielkiego pecha w wielce
>
> > dlugiej serii - bo wtedy stos sie wywali - ale taki pech jest malo
>
> > prawdopodobny
>
>
>
> Dowolna, czy si� j� jako� wybiera? Nie mo�na robi�c te swapy na lewo
>
> i prawo policzy� sobie �redniej przy okazji?
>
>
mysle ze mozna, pomysl dobry, ale trzebbby
bylo sprawdzic czy jest korzystne

mozna tez pewnie przed startem wziac trzy
albo piec i wybrac srodkowa itp

jesli wszystko jest w miare losowe to
podzialybylyby tak jak dzielic rekurencyjnie
losowo odcinek na dwie czesci czyli szloby
dosyc szybko pewnie x*=0.75

zreszta brzegi tez chyba mozna tam
wykorzystac - ale to sa szczegoly nie
bardzo mam chec teraz pisac sobie wuicksorta,
sortowania uzylem raz w zyciu 5 lat temu

jakbym pisal teraz sorta to zrobilbym
'kasperskim' i jak juz to mz bardziej
warto pomyslec nad uogolnieniem onegoż
na przypadki z zakresu wiecej niz np
milion np dla 32 bit 4 mlrdy - ale to tez
kiedy indziej

do góry

Dnia Sat, 13 Oct 2012 11:16:55 -0700, kenobi napisal:

> W dniu sobota, 13 października 2012 20:01:01 UTC+2 użytkownik Edek Pienkowski
napisał:
>> Dnia Sat, 13 Oct 2012 10:50:01 -0700, kenobi napisal:
>>
>>
>>
>> >>
>>
>> >> No to ju� brzmi fajnie. A co to by�o to C, kt�ra warto�� to ma by�?
>>
>> >>
>>
>> >> Poza tym, czy swap�w nie mia�o by� jak najmniej?
>>
>> >>
>>
>> >>
>>
>> > C to dowolna wartosc z tablicy najlepiej gdyby to byla taka ktora podzieli
>>
>> > tablice na dwa zblizone wielkoscia kawalki, mozna wylosowac dowolna np ze
>>
>> > srodka przedzialu, wazne tylko by nie miec wielkiego pecha w wielce
>>
>> > dlugiej serii - bo wtedy stos sie wywali - ale taki pech jest malo
>>
>> > prawdopodobny
>>
>>
>>
>> Dowolna, czy si� j� jako� wybiera? Nie mo�na robi�c te swapy na lewo
>>
>> i prawo policzy� sobie �redniej przy okazji?
>>
>>
> mysle ze mozna, pomysl dobry, ale trzebbby
> bylo sprawdzic czy jest korzystne
>
> mozna tez pewnie przed startem wziac trzy
> albo piec i wybrac srodkowa itp
>
> jesli wszystko jest w miare losowe to
> podzialybylyby tak jak dzielic rekurencyjnie
> losowo odcinek na dwie czesci czyli szloby
> dosyc szybko pewnie x*=0.75
>
> zreszta brzegi tez chyba mozna tam
> wykorzystac - ale to sa szczegoly nie
> bardzo mam chec teraz pisac sobie wuicksorta,
> sortowania uzylem raz w zyciu 5 lat temu
>
> jakbym pisal teraz sorta to zrobilbym
> 'kasperskim' i jak juz to mz bardziej
> warto pomyslec nad uogolnieniem onegoż
> na przypadki z zakresu wiecej niz np
> milion np dla 32 bit 4 mlrdy - ale to tez
> kiedy indziej

Kasperski to ten od szachów czy od antywira?

No ale ok, liczy się średnią stringa, ale czegoś tu nie rozumiem.
Jak się wybiera dowolne C to które, przez rand? I jak to jest,
że ma się na końcu wszystko posortowane?

--
Edek

do góry

W dniu sobota, 13 października 2012 20:22:02 UTC+2 użytkownik Edek Pienkowski
napisał:
> Dnia Sat, 13 Oct 2012 11:16:55 -0700, kenobi napisal:
>
>
>
> > W dniu sobota, 13 października 2012 20:01:01 UTC+2 użytkownik Edek Pienkowski
napisał:
>
> >> Dnia Sat, 13 Oct 2012 10:50:01 -0700, kenobi napisal:
>
> >>
>
> >>
>
> >>
>
> >> >>
>
> >>
>
> >> >> No to ju� brzmi fajnie. A co to by�o to C, kt�ra warto�� to ma
byďż˝?
>
> >>
>
> >> >>
>
> >>
>
> >> >> Poza tym, czy swap�w nie mia�o by� jak najmniej?
>
> >>
>
> >> >>
>
> >>
>
> >> >>
>
> >>
>
> >> > C to dowolna wartosc z tablicy najlepiej gdyby to byla taka ktora podzieli
>
> >>
>
> >> > tablice na dwa zblizone wielkoscia kawalki, mozna wylosowac dowolna np ze
>
> >>
>
> >> > srodka przedzialu, wazne tylko by nie miec wielkiego pecha w wielce
>
> >>
>
> >> > dlugiej serii - bo wtedy stos sie wywali - ale taki pech jest malo
>
> >>
>
> >> > prawdopodobny
>
> >>
>
> >>
>
> >>
>
> >> Dowolna, czy si� j� jako� wybiera? Nie mo�na robi�c te swapy na lewo
>
> >>
>
> >> i prawo policzy� sobie �redniej przy okazji?
>
> >>
>
> >>
>
> > mysle ze mozna, pomysl dobry, ale trzebbby
>
> > bylo sprawdzic czy jest korzystne
>
> >
>
> > mozna tez pewnie przed startem wziac trzy
>
> > albo piec i wybrac srodkowa itp
>
> >
>
> > jesli wszystko jest w miare losowe to
>
> > podzialybylyby tak jak dzielic rekurencyjnie
>
> > losowo odcinek na dwie czesci czyli szloby
>
> > dosyc szybko pewnie x*=0.75
>
> >
>
> > zreszta brzegi tez chyba mozna tam
>
> > wykorzystac - ale to sa szczegoly nie
>
> > bardzo mam chec teraz pisac sobie wuicksorta,
>
> > sortowania uzylem raz w zyciu 5 lat temu
>
> >
>
> > jakbym pisal teraz sorta to zrobilbym
>
> > 'kasperskim' i jak juz to mz bardziej
>
> > warto pomyslec nad uogolnieniem onegoż
>
> > na przypadki z zakresu wiecej niz np
>
> > milion np dla 32 bit 4 mlrdy - ale to tez
>
> > kiedy indziej
>
>
>
> Kasperski to ten od szachów czy od antywira?
>
>
>
> No ale ok, liczy się średnią stringa, ale czegoś tu nie rozumiem.
>
> Jak się wybiera dowolne C to które, przez rand? I jak to jest,
>
> że ma się na końcu wszystko posortowane?
>



pomysl i popatrz na przyklady to zalapiesz
ja nie mam czasu na zbyt dlugie gadki na ten
temat bo mam niesty co innego do roboty
niz setny raz w zyciu pilowac quicksorta
(a robilem to juz pare razy w zyciu)



mowilem juz ze 3 razy jak po 1 przebiegu masz

mmmmmmmmmmmmmmmwwwwwwww
<
gdze wszystkie m < w (m nie sa monotoniczne
ale na pewno kazde w czesci m jest mniejsza
od kazdej w czecci w )

to po drugim przebiegu jest

aaaaaaaammmmmmmmwwwwwwzz
< < <
jak sie dojedzie w 10tym przebiegu to te
przedzaly juz sa pojedynczymi liczbami
i
<<<<<<<<<<<<<<<<<<<<<<<<<

do góry

W dniu sobota, 13 października 2012 19:37:28 UTC+2 użytkownik kenobi napisał:
> oczywiscie i tak jest to slamazarstwo
>
> najlepsze sortowanie to to co ja nazywam
>
> metoda chrissa kaserskiego, czyli
>
>
>
> h[ tab[i] ]++;
>
>
>
> Podobno kiedys zrobil tak na jakiejs
>
> olimpiadzie jako nastolatek i komisja
>
> mu tego nie uznala ;-) zarabista anegdota
>
> (pisalem o tym z rok czy dwa temu)
>
>
>
> Mozna to uogolnic np w h(tab[i])
> robiac galaz drzewa, albo innymi metodami
> i mysle ze to raczej jest po prostu najszybsze

za jakis czas sobie klepne pewnie to
uogolnienie, np dla 32 bit mozna pewnie
w jednym przebiegu zrobic histogram na
gornych bitach wygenerowac czesciowo
uporzadkowany wynik i w kolejnym posortowac
kawalki, albo tez i inaczej ladnie
dobierajac po efektywnosci - w kazdym
razie raczej da sie to uogolnic :U

razie

do góry

Dnia Sat, 13 Oct 2012 11:47:57 -0700, kenobi napisal:

>> No ale ok, liczy się średnią stringa, ale czegoś tu nie rozumiem.
>>
>> Jak się wybiera dowolne C to które, przez rand? I jak to jest,
>>
>> że ma się na końcu wszystko posortowane?
>>
>>
>
>
> pomysl i popatrz na przyklady to zalapiesz ja nie mam czasu na zbyt dlugie
> gadki na ten temat bo mam niesty co innego do roboty niz setny raz w zyciu
> pilowac quicksorta (a robilem to juz pare razy w zyciu)

Wiem, ale od zawsze chciałem wiedzieć, a nikt nie chce mi przybliżyc tematu.
Przynajmniej dostałem kilka fajnych przykładów i wiem, że muszę zmienić
sposób mojego podejścia, myślenie kategoriami takimi jakie znam
z innych algorytmów takie jak "partycjonowanie rekurencyjne odpowiednie
do zrównoleglania oraz lokalne" to jakieś mumbo-jumbo, sam przyznasz.
Dostaję przykład kodu i nie od razu jestem go w stanie zrozumieć,
taki tego skutek, czytałem jakieś opisy ale nawet ruchome obrazki
nie pozwalają mi zrozumieć, o co tu chodzi. A to N log N to już jakaś
magia jak dla mnie. Co do stack overflow przy spreparowanych danych
to już wyższa jazda dla mnie, naprawdę da się w ten sposób włamać?
Taki "quick-break-in"?

> mowilem juz ze 3 razy jak po 1 przebiegu masz
>
> mmmmmmmmmmmmmmmwwwwwwww
> <
> gdze wszystkie m < w (m nie sa monotoniczne ale na pewno kazde w czesci m
> jest mniejsza od kazdej w czecci w )
>
> to po drugim przebiegu jest
>
> aaaaaaaammmmmmmmwwwwwwzz
> < < <
> jak sie dojedzie w 10tym przebiegu to te przedzaly juz sa pojedynczymi
> liczbami i
> <<<<<<<<<<<<<<<<<<<<<<<<<

Aha, faktycznie. Ale przeczytałem poprzednie posty, i nie rozumiem co
się z czym swapuje. Ten element C z początek(++)? I co z C, jak już jest
na początku(++)?

--
Edek

do góry