[Algorytmy] Sortowanie - minimalna liczba porownan

[snd0cff]

1. Jaka jest minimalna liczba porownan potrzebna do znalezienia dowolnego elementu w \(\displaystyle{ 64}\) elementowym zbiorze uporzadkowanym?

Odpowiedz to \(\displaystyle{ 6}\), ale jak do tego dojsc?

[Althorion]

\(\displaystyle{ \log_2 64 = 6}\). Zaczynasz od środka. Jeśli liczba jest mniejsza, to wybierasz tę połowę tablicy, która zawiera większe liczby, jeśli nie, to na odwrót. Powtarzasz do znalezienia szukanej liczby.

[snd0cff]

Jeszcze mam jedno pytanie:
Jak bedzie uporzadkowany nastepujacy zbior liczb \(\displaystyle{ \{5,11,4,9,3\}}\) po pierwszym etapie dzialania sortowania "szybkiego"

Z tego co wiem(a przynajmniej tak zinterpretowalem tekst) to bierzemy \(\displaystyle{ 4}\) (srodkowy wyraz) i na lewo liczby mniejsze \(\displaystyle{ (3)}\), a na prawo wieksze \(\displaystyle{ (5,11,9)}\) w takiej kolejnosci jak sa podane w zbiorze i wychodzi:
\(\displaystyle{ 3,4,5,11,9}\)
Co robie nie tak?

[Althorion]

Nic, wszystko w porządku. Z tym że sam algorytm nic nie mówi o tym, który element brać jako rozgraniczający, zależy to od implementacji. Często bierze się pierwszy, środkowy (jak Ty to robisz), ostatni, losuje się albo specjalnie szuka najpierw mediany.

[royas]

Mam wątpliwość co do odpowiedzi na pierwsze pytanie. Bo to raczej pokazanie, że 6 wystarcza, a raczej trzeba pokazać, że nie istnieje algorytm, który by dla każdych danych potrzebował mniej niż 6.
Czyli, że nie istniej o mniejszej złożoności pesymistycznej.

[Althorion]

To raczej szkic dowodu w obu przypadkach. Żeby go wzmocnić, musimy się powołać na fakt, że jeśli nie dzielimy danych na połowy, to pesymistycznie za każdym razem może nam szukana wartość wypadać w tej większej części; tak więc aby zminimalizować czas działania algorytmu należy dążyć do tego, by te części były równe.