RandomSelect

Description

RandomSelect wykorzystuje podejście zaprezentowane w algorytmie QuickSort. Jest to algorytm, który w najgorszym przypadku będzie działał w złożoności $O(n^2)$, ale jeśli założymy, ze wejściowa tablica $A$ jest losową permutacją wielkości $n$ to można pokazać, że $E$ (wartość oczekiwana) zmiennej losowej $X$ liczby porównań wynosi $O(n)$ (robi się to w podobny sposób jak to było w przypadku QuickSorta).
Algorytm ten jest tylko drobną modyfikacją algorytmu do wyznaczania mediany (2.4 Medians).

Więcej informacji tutaj 9.2.