Пошук порядкової статистики

${\displaystyle \;FindMaxMin(A)}$
1. ${\displaystyle min\leftarrow A[1]}$
2. ${\displaystyle max\leftarrow A[1]}$
3. ${\displaystyle i\leftarrow 2}$
4. if ${\displaystyle \;length[A]\mod 2=0}$
5.    then if ${\displaystyle \;A[2]>max}$
6.            then ${\displaystyle max\leftarrow A[2]}$
7.            else ${\displaystyle min\leftarrow A[2]}$
8.         ${\displaystyle i\leftarrow 3}$
9. while ${\displaystyle i\leq length[A]}$
10.      do ${\displaystyle j\leftarrow i}$
11.         ${\displaystyle k\leftarrow i+1}$
12.         if ${\displaystyle \;A[j]>A[k]}$
13.            then Поміняти ${\displaystyle j\leftrightarrow k}$
14.         if ${\displaystyle A[j]<min\;}$
15.            then ${\displaystyle min\leftarrow A[j]}$
16.         if ${\displaystyle A[k]>max\;}$
17.            then ${\displaystyle max\leftarrow A[k]}$
18.         ${\displaystyle i\leftarrow i+2}$

Така оптимізація доцільна у випадках, коли порівняння елементів з множини A займає багато часу. Наприклад, якщо порівнюється текст або графічні зображення.

Функція ${\displaystyle Partition(A,p,q)}$ виконує розділення частини масиву з p-го по q-й елемент на дві менші частини.

${\displaystyle Partition(A,p,q)\;}$
1 ${\displaystyle x\gets \;A[q]}$
2 ${\displaystyle i\gets \;p-1}$
3 for ${\displaystyle j\gets \;p}$ to ${\displaystyle \;q-1}$ 
4 do  if ${\displaystyle A[j]\leq \;x\;}$
5     then ${\displaystyle i\gets \;i+1}$
6          Поміняти ${\displaystyle A[i]\leftrightarrow \;A[j]}$
7 ${\displaystyle i\gets \;i+1}$
8 Поміняти ${\displaystyle A[i]\leftrightarrow \;A[q]}$
9 return ${\displaystyle \;i}$

Функція ${\displaystyle Randomized\_Partition(A,p,q)}$ Робить те ж саме, але вносить рандомізацію в поділ.

${\displaystyle Randomized\_Partition(A,p,q)\;}$
1 ${\displaystyle i\leftarrow Random(p,q)}$
2 Поміняти ${\displaystyle A[i]\leftrightarrow A[q]}$
9 return ${\displaystyle \;Partition(A,p,q)}$

Сам пошук k-ї статистики в масиві A здійснюється функцією ${\displaystyle Randomized\_Select(A,1,length[A],k)}$

${\displaystyle Randomized\_Select(A,p,q,k)\;}$
1. if ${\displaystyle \;p=q}$
2.    then return ${\displaystyle \;A[p]}$
3. ${\displaystyle r\leftarrow Randomized\_Partition(A,p,q)}$
4. ${\displaystyle t\leftarrow r-p+1}$
5. if ${\displaystyle \;k=t}$
6.    then return ${\displaystyle \;A[r]}$
7. elseif ${\displaystyle \;k<t}$
8.    then return ${\displaystyle \;Randomized\_Select(A,p,r-1,k)}$
9.    else return ${\displaystyle \;Randomized\_Select(A,r+1,q,k-t)}$

В найкращому випадку (за умови розбиття на рівні частини), час роботи пошуку описується рівнянням:

${\displaystyle \;T(n)=T\left({\frac {n}{2}}\right)+O(n)=O(n)}$

Середній час роботи також є${\displaystyle \;O(n)}$, і завдяки рандомізації швидкість роботи на довільному вході близька до середньої. Якщо ж розбиття вибрано погано то в найгіршому випадку складність буде ${\displaystyle \;O(n^{2})}$

Час на впорядкування всіх маленьких частин масиву і час на розбиття масиву є O(n). Вибір елемента розбиття x гарантує, що в більшу частину попаде не більше 7n/10+6 елементів. Отже, рівняння для часу роботи є:

${\displaystyle T(n)=T\left(\left\lceil {\frac {n}{5}}\right\rceil \right)+T\left({\frac {7n}{10}}+6\right)+O(n)=O(n)}$