Jak mamy znaleźć 3-ci element w tym ciągu:
7,2,4,3,6,8,1,5,9 (przyjmujemy że sortujemy wg pierwszego elementu, 3-ci element tu to "3")
Po 1. posortowaniu wg 1. elementu mamy: 2,4,3,6,1,5,(7),8,9 - 3-ci element znajduje się w 1. części więc drugą część odrzucamy, otrzumując: 2,4,3,6,1,5
Po 2. posortowaniu mamy: 1,(2),4,3,6,5 - 3-ci element znajduje się w 2. części więc 1. odrzucamy: 4,3,6,5
Po 3. posortowaniu mamy: 3,(4),6,5 - 3-ci element wychodzi na to, że znajduje się w 2. części a to nieprawda - co robie źle ?
0
0
Ten ich algorytm jest jakiś dziwny: najpierw dwa razy partitioning i szukanie elementu "k" a potem kolejne partitioningi i szukanie elementu: "k" minus liczność zbioru liczb mniejszych ?
0
Szukając n-tego elementu, jeśli odrzucasz lewą część składającą się z m elementów, to dalej szukasz (n-m)-tego elementu.
Np. w 2 kroku odrzuciłeś 1-ke i 2-ke. Czyli odrzuciłeś 2 elementy z lewej, zatem dalej nie szukaj 3-ciego a (3-2)-go czyli pierwszego elementu.
0
Wielkie dzięki adf88 teraz wreszcie rozumiem :)