W dniu niedziela, 14 października 2012 00:59:41 UTC+2 użytkownik PK napisał:
> > algorytm dla 5. Dużo ifów:)
> > Dlaczego dla 5? Bo w mamy algorytm magicznych piątek;)
> > Dla 20 byłby już zbyt skomplikowany. Za duży.
> Duży to kwestia względna. Napisanie (wygenerowanie) nie kosztuje
> zupełnie nic. Pozostaje kwestia rozmiaru programu, ale to nie
> zawsze jest problem.
Moim zdaniem, na wspolczesnych procesorach, ktore maja duza roznica pomiedzy
dostepem do danych w cache i poza cache, bedzie jednak stanowilo problem.
Strzelam ze bedzie 3krotne spowolnienie liniowe z powodu rozmiaru programu.
Pozdrawiam
PS.
20 danych to 512k instrukcji if i tyle samo instrukcji else?

do góry

W dniu 2012-10-14 01:16, PK pisze:
> On 2012-10-13, bartekltg <b...@g...com> wrote:
>> Co daje 2^62 możliwych wyników - gałęzi algorytmu.
>
> Niestety nie wiem co nazywasz "gałęzią algorytmu".
> Drzewo decyzyjne ma unikatowe liście, czyli jest ich 20!.

Zgadza się.

>> Jeśli zamieniasz elementy miejscami by zmniejszyć tą
>> ilość, już wykonujesz niepotrzebne operacje.
>
> W drzewku decyzyjnym nie ma niepotrzebnych operacji. Na tym polega
> ta idea. Chyba nie łapiesz o czym piszę :).

Tak. Ale teraz mówimy o implementacji.
Nie zaimplementujesz takiego pełnego drzewa
z 20! ~ 2^ 62 liścmi w pełni.

>
>> Dla 20 można taki algorytm napisać, ale jest on chyba
>> dość teoretycznym tworem.
>> Dla 4 i 5 to się takie rzeczy pisało, ale dla 20...
>
> Teretycznym nie, bo ktoś to już napisał (istnieją wyniki).

Dla 20?

> Nie mniej w tym algorytmie nie chodzi o optymalizację, tylko
> o wyznaczenie dolnego ograniczenia. Poza tym o tę głównie o tę
> ideę są oparte sorty sprzętowe (dla tych, którzy nie chcą tracić
> czasu na niepotrzebne operacje komputerów :)).

Teoretycznie to ja rysuję drzewo i nie muszę tego
implementować;)
Sprzętowe sortowanie za pomocą pełnego drzewa decyzyjnego
dla 20 liczb? Jaja sobie robisz? ;) Oszczedza się kompa,
ale trzeba tone krzemu.

BTW, nie robi się tego za pomocą tworu zwanego siecią sortującą?

Nie chodzi o optymalizację? przecież zaczęło się do stwierdzenia
'potrzebuję posortować dużo 20, to biore optymalny algorytm
dla 20 elementów'

> Zresztą istnieje algorytm (Ford & Johnson Merge-Insertion Sort),
> który dla małych n jest bliski optymalnemu (i tym samym jest
> zapewne najlepszym algorytmem dla krótkich ciągów). Dla n=20
> akurat jest optymalny. Polecam poszukać, bo to naprawdę nieźle
> wyrzeźbiona rzecz :).

Ładny. Ale widzisz różnicę między nim, a pełnym drzewem.
To się mieści w RAMie lub krzemie;)

pzdr
bartekltg

do góry

W dniu 2012-10-14 01:22, PK pisze:
> On 2012-10-13, bartekltg <b...@g...com> wrote:
>> Ale dla 20? Bez sztuczek to nam się nie tylko w cache,
>> ale i w RAMie nie zmieści.
>
> Bez sztuczek nie, ale można to podzielić. Nie mniej wtedy oczywiście
> są jakieś straty na dodatkowe kombinowanie, więc może się przestać
> opłacać.
>
>>
>> Możesz powiedzieć coś więcej o tych praktycznych zastosowaniach,
>> jak wygląda implementacji i do jakich liczb to się stosuje?
>
> Widziałem zastosowania dla n=8 (zarówno soft- jak i hardware). Akurat
> było to zastosowanie w fizyce (tam się trochę spieszą). Nie wiem czy
> istnieje jakiekolwiek inne zastosowanie, gdzie ludzie tak walczą
> o nanosekundy - może w jakimś GPS czy innych militariach?

A nie robili tego siecią?
Optymalna sieć sortująca dla 8 ma 19 komparatorów i, co znacznie
tam ważniejsze, głębokość 6. Czyli posortowany ciąg wypada po
czasie 6 sortowań.

pzdr
bartekltg

do góry

Dnia Sun, 14 Oct 2012 00:41:44 +0200, bartekltg napisal:

> W dniu 2012-10-13 16:58, Edek Pienkowski pisze:
>> Dnia Sat, 13 Oct 2012 16:13:55 +0200, bartekltg napisal:
>>
>>> W dniu 2012-10-13 16:13, Edek Pienkowski pisze:
>>>
>>>>
>>>> Peephole - o ile wszyscy rozumieją przez to to samo - to zbiór drobynch
>>>> optymalizacji kodu przeprowadzanych na niewielkim fragmencie kodu, stąd
>>>> przynajmniej jest nazwa. Jest to optymalizacja obecna we wszystkich
>>>> optymalizujących kompilatorach, niektóre robią ją kilka razy tak
>>>> dla oczyszczenia, bo po to głównie jest.
>>>
>>> Ok, to wiem, ale... przecież to nie na temat.
>>>
>>> Pytamy się, co byś polecił na zapoznanie się z algorytmiką,
>>> a ty odpowiadasz 'szukanie wąskich gardeł'. To jest bardzo
>>> pożyteczne i rozwijające zajęcie, ale algorytmika jest o czym innym.
>>
>> Shite. To powiedz mi, o czym jest algorytmika.
>
> Zawsze myslalem o tym, jako o nauce projektowania algorytmów.
> Ale nie mikroptymalizacji, tylko takim bardziej ogolnym.

Po pierwsze, kompilatory robią masę "mikrooptymalizacji".
Implementuje się je raz.

No i to są algorytmy, niektóre dość proste, więc to jest
wstęp do algorytmiki, jeden z możliwych. Uczy wszystkich
podstawowych elementów dorzucając model procesora, którego
trzeba użyć. RAMu i cache może nie mieć, ze dwa rejestry
i proste fikcyjne ALU, pełny minimalizm.

> Obok jest dyskusja o qsorcie. Na takiej algorytmice student na dzien
> dobry ląduje z qsortem. Ma załapać ideę. Robimy podział
> porządkujący, i odpalamy rekurencyjnie.
> Ma rozumieć, dlaczgo to prowadzi do szybkiego posortowania.
>
> Od tego, czy będzie tam warunek sprawdzający zakres, czy
> student sobie poradzi bez niego, ważniejsze będzie
> zrozumienie niezmienników.

A moim zdaniem musi go spróbować zaimplementować sam wcześniej.
Albo coś podobnego. Ucz małpę niezmienników ;)

>> Ten sam problem: nie wiem - jak widać - co to jest algorytmika. Przynajmniej
>> ta "czysta". Nie potrafię ekstrapolować z sorta, jedynego w takim razie
>> przykładu, że to algorytmika.
>
> Myślę, że tu nie chodzi o sorta, tylko o nauczenie pewnego
> zestawu narzędi i sposobu myślenia _przydatnego_ przy
> projektowaniu algorytmów.
> Podstawy analizy zlozonośći, myślenie o niezmiennikach,
> ale też zwracanie uwagi na sytuacje krańcowe
> ("Z pętlą jest jak z lotem samolotem. Najtrudniejszy jest
> start i lądowanie. Sam lot jest stosunkowo prosty"//Diks;))

No, nawet myśle podobnie, ale wciąż nie kumam o co chodzi
z tym sortem.

>> Widziałem prace z obu tematów w kwestii rozwiązywania problemów NP-hard
>> i uważałem to za algorytmikę, ale już teraz nic nie wiem.
>
> Wiesz, ludzie pisząc prace z analizy atakują równie trudne problemy.
> Ale jednak analiza na pierwszym roku to całki i różniczki.
> I to całki i różniczki, czyli 200-300 letnie podstawy będą
> potrzebne inżynierom, nie najnowsze wyniki w sprawie istnienia
> rozwiązań równań naviera-stokesa;)
>
> Chociaż masz trochę racji. Mówimy na to popularnie
> algforytmika, a takin MIM nazywa to algorytmi
> i struktury danych. Algorytmika to osobny przedmiot,
> semestr później i tam robi się druga polowę Cormena
> (czyli właśnie m.in wspomina o tych zawansowanych
> problemach z klasami obliczalnosci).

Mi nie chodzi o to "czy uczyć całki", ale "jak uczyć całki". To samo
w kwestii algorytmów, czy bądźmy szczerzy: programowania.

>>> Ok, nieważne
>>
>> Zazwyczaj nie gadasz bzdur, więc moze czegoś się dowiem.
>
> :)
> Ale ostrzegam, ja nie jestem prawdziwym informatykiem.

Przyszywanym bardziej niż ja nie jesteś. Ale jakoś dajesz radę?

>> Przeczytałem wikipedię polską i angielską - poza tym, że polska mówi o
>> etymologii z XIX wieku a angielska o XII w. i nadużyciu słowa w XIX - nic
>> się nie dowiedziałem. Znalazłem tylko tą definicję z "... worker/solver
>> moving around a problem vector space ...", taką bliską sercu.
>
> Trochę nam chyba ucieka dyskusja. Ustalać definicji algorytmiki
> się nie podejmuję. Pozostańmy przy tym, z czym zapoznać studenta
> w ramach takiego przedmiotu.
>
> Ja uważam, że powinno się ich nauczyć metod pomocnych
> w atakowaniu problemów niesprowadzających się wprost
> do 'wpakuj do kontnera i posortuj'.

Dajesz mi argumenty?

> Powiedzmy, okolice średniej trudności z tego:
> http://potyczki.mimuw.edu.pl/user.phtml?op=zadania

Przejrzałem trzy. Wieże akurat nie są problemem, bo gram
szachy. Ten z odwiedzaniem miast ciekawszy. Ten z drzewem
jako "<bardzo ciekawa definicja>" też da się sprowadzić
do trywialnego. Wszystkie uczą rozwiązywania problemów,
to takie logiczne zagadki, a z narzędzi informatycznych
nadają się na "napisz coś co robi co wymyślisz". Niezłe,
ale spotkałem lepsze: durny peephole, który wielkim problemem
logicznym nie jest. Tak z innego poziomu: peephole uczy
programowania na przykładzie przekształcania programu,
przy okazji ucząc prostej optymalizacji (znowu: mało
kto będzie pisał kompilator, więc jest bardziej
abstrakcyjne niż te szachy).

> No i oczywiście uświadomienie istnienia pewngo pakietu
> znanych algorytmów. Takie find-union czy drzewa
> przedziałowe przydają się czasem, a w STL ich nie ma.
> Pewnie są w boost, ale trzeba wiedzieć, czego szukać.

Jak będę ich potrzebował, to będę o tym wiedział. Na dzisiaj
mam co innego na głowie, i stwierdzam, że w tej kwestii
tak było nie tylko dzisiaj, ale dotychczas zawsze. Union
się mi prawdopodobnie zdarzył.

Jest masę różnych algorytmów, o których człowiek nie wie.
Ja się na przykład kiedyś natknąłem na takie: jak
zrealizować w systemie rozproszonym decyzję, który node
ma największą liczbę mając do dyspozycji atomiczne
rejestry (inne prace pokazały niezawodną implementację)
i Omegę, która daje każdemu node'owi pewną informację
na temat tego, czy pozostałe node'y jeszcze dychają.
Komunikacja jest typu "messaging", algorytm ma się
skończyć w skończonym czasie. Problem polega na
znalezieniu ściśle słabszej wyroczni (słabsza
to taka, że z silniejszej da się wyprowadzić słabszą;
"ściśle", że odwrotne jest niemożliwe). Niektórych
Omeg nie jestem w stanie odtworzyć tak były pokręcone,
a co tu mówić o wymyślonych algorytmach. A, i mają zastosowanie,
chociaż nie wszystkie.

"My point is": można dać studfentowi kilka popularnych
algorytmów, i tak użyje części a inne musi albo
znaleźć, albo wymyśleć samemu. Jednemu wystarczy to
za wstęp do algorytmów, innemu nie, i różnica nie
polega na wiedzy tylko umiejętnościach.

--
Edek

do góry

On 14.10.2012 00:51, PK wrote:
> Sortowanie optymalne: max 62 porównania.
To rozwiązanie jest optymalne tylko jeżeli chodzi o liczbę porównań[*].
A nie np. czas, czy pamięć na rzeczywistym systemie(czy nawet na
abstrakcyjnej maszynie).

Możemy rozważyć mergesort na 10 procesorach - wykona trochę więcej
porównań niż Twoje "optimum", ale za to zakończy pracę prawie 2 razy
szybciej ;)

[*] Na typach bez znaku możemy sortować po kolejnych bitach. Nie
wykonujemy w takim przypadku porównań między liczbami a szukamy
pierwszej liczby z zapalonym n-tym bitem po lewej i niezapalonym po
prawej, zamieniamy, powtarzamy aż do spotkania indeksów. Powtarzamy
rekurencyjnie dla obu kawałków i n-1 bitu. Mamy 0 porównań - to dopiero
optimum ;)

--
Pozdrawiam
Michoo

do góry

W dniu niedziela, 14 października 2012 01:33:48 UTC+2 użytkownik bartekltg napisał:
> Teoretycznie to ja rysuję drzewo i nie muszę tego
> implementować;)
> Sprzętowe sortowanie za pomocą pełnego drzewa decyzyjnego
> dla 20 liczb? Jaja sobie robisz? ;) Oszczedza się kompa,
> ale trzeba tone krzemu.
Jak duze musi byc pelne drzewo decyzyjne? Poczatkowo mamy N! mozliwych
permutacji. Pierwsza instrukcja IF powoduje ze mam pewnosc co do
kolejnosci dwoch elementow. Jesli N==20, to po pierwszym IF nie
wiemy nic o 18tu elementach. Daje to 18! ciagow. Pozostale dwa elementy
moga byc wplecione w te 18 na 19*19 sposobow. 20! / ( 18! * 19^2 ) = 1.0526.
Po pierwszym IFie ilosc permutacji spadla o okolo 5%. O ile spadnie z
kazdym nastepnym ifem?
Pozdrawiam




>
>
>
> BTW, nie robi się tego za pomocą tworu zwanego siecią sortującą?
>
>
>
> Nie chodzi o optymalizację? przecież zaczęło się do stwierdzenia
>
> 'potrzebuję posortować dużo 20, to biore optymalny algorytm
>
> dla 20 elementów'
>
>
>
> > Zresztą istnieje algorytm (Ford & Johnson Merge-Insertion Sort),
>
> > który dla małych n jest bliski optymalnemu (i tym samym jest
>
> > zapewne najlepszym algorytmem dla krótkich ciągów). Dla n=20
>
> > akurat jest optymalny. Polecam poszukać, bo to naprawdę nieźle
>
> > wyrzeźbiona rzecz :).
>
>
>
> Ładny. Ale widzisz różnicę między nim, a pełnym drzewem.
>
> To się mieści w RAMie lub krzemie;)
>
>
>
> pzdr
>
> bartekltg

do góry

Dnia Sat, 13 Oct 2012 16:25:09 -0700, M.M. napisal:

> W dniu niedziela, 14 października 2012 00:59:41 UTC+2 użytkownik PK napisał:
>> > algorytm dla 5. Dużo ifów:)
>> > Dlaczego dla 5? Bo w mamy algorytm magicznych piątek;)
>> > Dla 20 byłby już zbyt skomplikowany. Za duży.
>> Duży to kwestia względna. Napisanie (wygenerowanie) nie kosztuje
>> zupełnie nic. Pozostaje kwestia rozmiaru programu, ale to nie
>> zawsze jest problem.
> Moim zdaniem, na wspolczesnych procesorach, ktore maja duza roznica pomiedzy
> dostepem do danych w cache i poza cache, bedzie jednak stanowilo problem.
> Strzelam ze bedzie 3krotne spowolnienie liniowe z powodu rozmiaru programu.
> Pozdrawiam
> PS.
> 20 danych to 512k instrukcji if i tyle samo instrukcji else?

Pewnie w hardware nie ma tego typu problemu. Było wspomniane.

A skoro mowa o wywoływanym miliard razy sortowaniu, mówimy o L1
i branch prefiction. Procesor powinien mieć co najmniej kolejny
poziom jak nie kilka już zasysany albo do L1 albo już wykonywany
w core. Trzeba zmierzyć, ale L1<->L2 dzisiaj to lepiej niż 1e11 B/s,
bo tyle to ma RAM. Policzyć tez by można:
- przepustowośc to tak pi razy oko 1e6/1e12 = 5e-7
- instrukcje n(n-1)/2 ot nie lepiej niż 20*19/2 / 3e9 =~ 200/3e9 ~= 6e-8

To może masz rację, ale trzeba zmierzyć.

--
Edek

do góry

On 13.10.2012 14:27, PK wrote:
> On 2012-10-13, Michoo<m...@v...pl> wrote:
>> Jeżeli dobrze widzę to i insertion i selection może być stabilny.
>
> *Każdy* algorytm sortowania można uczynić stabilnym. Rzecz w tym, że
> część są stabilna od razu, a w niektórych wymaga to małych nakładów.
> I są też takie, z którymi walczyć nie warto :).
Uczyń stabilnym algorytm zaproponowany w punkcie Example
http://www.sgi.com/tech/stl/next_permutation.html

--
Pozdrawiam
Michoo

do góry

W dniu 2012-10-14 02:01, Edek Pienkowski pisze:

>> Zawsze myslalem o tym, jako o nauce projektowania algorytmów.
>> Ale nie mikroptymalizacji, tylko takim bardziej ogolnym.
>
> Po pierwsze, kompilatory robią masę "mikrooptymalizacji".
> Implementuje się je raz.

Ale pisanie kompilatora to zdecydowanie nie jest to, czym
się student pierwszego roku powinien zajmować:)


> No i to są algorytmy, niektóre dość proste, więc to jest
> wstęp do algorytmiki, jeden z możliwych. Uczy wszystkich
> podstawowych elementów dorzucając model procesora, którego
> trzeba użyć. RAMu i cache może nie mieć, ze dwa rejestry
> i proste fikcyjne ALU, pełny minimalizm.

To tu się po prostu nie zgadzamy. Zwykłym potrzeba
znaczniej bardziej tego sortowania niż babrania się
w asm. Zwłaszcza na początku.

Znam paru dobrych informatyków siedzących 'w przemyśle',
znam paru, ktorzy poszli w teorię. Na takim przedmiocie
JAJO, gdzie to właśnie mieli bawic się asm i bebechami
systemu poradzili sobie. Ale assembler jest im w codziennej
pracy niepotrzebny. Wiedza wyniesiona z analizy sortowania
- tak.



> A moim zdaniem musi go spróbować zaimplementować sam wcześniej.
> Albo coś podobnego. Ucz małpę niezmienników ;)

A co to za rożnica? Nie wymyślisz sam większośći algorytmów.
Często trzeba podsunać pomysł.

BTW, ja też przed studiami 'programowałem'. Bawilem sie pascalem,
C, C++. 16 bitoiwym assemblerem. Nawet na olimpiade
informatyczną się w liceum przejechałem.

A na studiach przeszedłem się po sąsiedzku na parę semestrów
różnych 'metod programowania' czy ASD i zrozumiałem,
jaką kaszanę odwalałem;)


>> Myślę, że tu nie chodzi o sorta, tylko o nauczenie pewnego
>> zestawu narzędi i sposobu myślenia _przydatnego_ przy
>> projektowaniu algorytmów.
>> Podstawy analizy zlozonośći, myślenie o niezmiennikach,
>> ale też zwracanie uwagi na sytuacje krańcowe
>> ("Z pętlą jest jak z lotem samolotem. Najtrudniejszy jest
>> start i lądowanie. Sam lot jest stosunkowo prosty"//Diks;))
>
> No, nawet myśle podobnie, ale wciąż nie kumam o co chodzi
> z tym sortem.

N qsorcie łumaczysz rekurencję. 'dziel i zwyciezaj".
Na takim insertionsorcie niezmienniki, pętle.
Porównując oba masz ilustrację złożonośći obliczeniowej.

Są to proste obrazki, przykłady do pojęć.

Można to zastąpić innymi, bardizej wymyslnymi algorytmami,
ale nijak nie da się tego zastąpić rzeźbieniem w asm
i peepholami. To po prostu inne zagadnienia.

Jedne cwiczenia na sortowanie można poswiecic.



>
> Mi nie chodzi o to "czy uczyć całki", ale "jak uczyć całki". To samo
> w kwestii algorytmów, czy bądźmy szczerzy: programowania.

A ja mam wrażenie, że pod jak uczyć całek mówisz
'uczmy się algebry'. Algebry tez się trzeba nauczyć,
ale na przedmiocie w sali obok. Teraz robimy całki.
Rozumiesz mnie?


> Przyszywanym bardziej niż ja nie jesteś. Ale jakoś dajesz radę?

A dziękuję, żyję. Ale bywało lepiej;]

> Dajesz mi argumenty?

A to źle?

>
>> Powiedzmy, okolice średniej trudności z tego:
>> http://potyczki.mimuw.edu.pl/user.phtml?op=zadania
>
> Przejrzałem trzy. Wieże akurat nie są problemem, bo gram
> szachy. Ten z odwiedzaniem miast ciekawszy. Ten z drzewem
> jako "<bardzo ciekawa definicja>" też da się sprowadzić
> do trywialnego. Wszystkie uczą rozwiązywania problemów,

Już nie pamiętam. Były tam i trudne. Tzn ja nie wymeśliłem
sprawnego sposobu, a z matmy dośc dobry jestem.

> to takie logiczne zagadki, a z narzędzi informatycznych
> nadają się na "napisz coś co robi co wymyślisz". Niezłe,
> ale spotkałem lepsze: durny peephole, który wielkim problemem
> logicznym nie jest. Tak z innego poziomu: peephole uczy
> programowania na przykładzie przekształcania programu,
> przy okazji ucząc prostej optymalizacji (znowu: mało
> kto będzie pisał kompilator, więc jest bardziej
> abstrakcyjne niż te szachy).

Tak, ale to są inne zagadnienia. Trzeba uczyć i jednych i
drugich. Nie jednych zamiast drugich.

>
>> No i oczywiście uświadomienie istnienia pewngo pakietu
>> znanych algorytmów. Takie find-union czy drzewa
>> przedziałowe przydają się czasem, a w STL ich nie ma.
>> Pewnie są w boost, ale trzeba wiedzieć, czego szukać.
>
> Jak będę ich potrzebował, to będę o tym wiedział. Na dzisiaj

Nie, jeśli nie jesteś świadomy istnienia czegoś, to
znacznie utrudnia znalezienie tego.
To pułapka wspolczesnie modnego poglądu na edukację,
by nie uczyć faktów.


pzdr
bartekltg

do góry

Dnia Sun, 14 Oct 2012 00:18:59 +0200, bartekltg napisal:

> W dniu 2012-10-13 20:06, Edek Pienkowski pisze:
>> 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?
>
>
> Oj, to wyższa filozofia;)
>
> Można wybierać z prawej, z lewej, ze środka,
> losowy element, medianę z końców i środka...
> Jak ktoś chce, może zawsze brać element 7
> (o ile tablica odpowiednio duża).
>
>
> BTW, algorytm dzielenia proponowany przez fira nie jest najlepszy.
> Raczej się robi to w ten sposób, że jedzie od początku w górę
> jednym indeksem, aż napotka się element za duży. Potem od końca
> w dół drugim indeksem, aż napotka się element za mały
> (mniejszy od elementu dzielącego). następnie zamienia się
> te elementy i wszytko powtarza, póki się indeksy nie spotkają.
>
> Do testów (i by sprawdzić, ile pamiętam, zajmuję się zupelnie
> innymi rzeczami) machnąłęm coś takiego:
>
> void qsort(int * tabl,int first, int last)
> {
> if (last-first>1)
> {
> int piv = tabl[first];//element dzielący
> int i=first; //elementow first i last+1
> int j=last+1; //nigdy nie dotkniemy
> do
> {
> do i++; while ((i<=last)&&(tabl[i]<piv));
> do j--; while (tabl[j]>piv); // fajne*)
> if (i<j) {std::swap(tabl[i],tabl[j])}
> }while (i<j);
>
> tabl[first]=tabl[j];
> tabl[j]=piv;
>
> qsort_insert(tabl, first, j-1);
> qsort_insert(tabl, j+1, last);
> }
> }
>
> Dzieki temu odpada jakaś polowa zapisów. W jednym ruchu swapa
> _dwa_ elementy lądują po odpowiednich stronach podziału.
>
> *) nie musimy sprawdzać zakresu, bo tab[first] go trzyma.
> podobnie, jeśli nasza tablica jest podtablicą taką, że
> tab[first-1] jest mniejsze, a tab[last+1] wieksze od kazdego
> elementu naszej tablicy, nie musimy tego sprawdzać.
> Zerknąłem do stla. Tam z tego korzystają i mają osobne
> procedury dla prawego kranca, lewego, i podtablicy wewnetrz.

Mi raczej chodziło o generalnie możliwość policzenia
średniej z dowolnych obiektów mających "strict weak ordering".
I fir przestał mnie uczyć quick-sorta :)

Trochę za późno dla mnie na czytanie kodu, może jutro ;)

--
Edek

do góry