[Algorytmy] rozdzielenie tablicy na dwie względem mediany
: 4 lis 2017, o 21:01
Mamy tablicę parzystej długości - \(\displaystyle{ A[2n]}\) - wypełnioną liczbami całkowitymi. Chcemy ją tak przestawić, by zachodziło \(\displaystyle{ A[k] \le A[j]}\) dla dowolnych \(\displaystyle{ k\le n ;j>n}\) (używam tu konwencji, że tablicę numerujemy poczynając od jedynki). Jak to zrobić w \(\displaystyle{ O(n)}\)? Wiadomo, że dla \(\displaystyle{ O(n\log (n))}\) wystarczy sobie posortować.