W dniu 2012-10-14 00:35, PK pisze:
> On 2012-10-13, kenobi <p...@g...com> wrote:
>> a jaki to jest ? ;-)
>
> Nie chodziło się na żaden wstęp do programowania ani nie czytało Knutha,
> co?
>
> Optymalny sort dla wektora liczb o znanej długości, to po prostu drzewo
> decyzyjne (binarne) z porównaniami elementów. Jeśli wykonujesz tylko
> konieczne porównania, to takie drzewo wyznacza Ci dolne ograniczenie dla
> pesymistycznych wariantów (czyli ile porównań zawsze wystarcza do
> posortowania n liczb).
>
> Okazuje się, że do posortowania 20 liczb wystarczają 62 porównania.

Co daje 2^62 możliwych wyników - gałęzi algorytmu.

Jeśli zamieniasz elementy miejscami by zmniejszyć tą
ilość, już wykonujesz niepotrzebne operacje.

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...

pzdr
bartekltg