Algorytm Hoare’a – prosty algorytm rozwiązujący problem selekcji. Problem selekcji polega na wyznaczeniu ${\displaystyle k}$-tej co do wielkości wśród ${\displaystyle n}$ liczb.

Algorytm

Algorytm Hoare’a opiera się na pomyśle podobnym co algorytm QuickSort, mianowicie na podziale zbioru na liczby mniejsze i większe od wybranego elementu. Nieprzypadkowo zresztą, pomysłodawcą obu algorytmów jest ten sam człowiek, C.A.R. Hoare.

Działanie algorytmu jest następujące, powiedzmy, że dany jest zbiór ${\displaystyle A}$ zawierający ${\displaystyle n}$ liczb. Zadanie polega na wybraniu ${\displaystyle k}$-tej co do wielkości. Wybieramy losową liczbę ${\displaystyle l}$ ze zbioru ${\displaystyle A}$ i dzielimy ten zbiór na elementy mniejsze lub równe od ${\displaystyle l}$ (zbiór ${\displaystyle A_{\leqslant }}$) oraz liczby większe od niej (zbiór ${\displaystyle A_{>}}$). Następnie, jeśli moc zbioru ${\displaystyle A_{\leqslant }}$ jest większa lub równa ${\displaystyle k,}$ to rekurencyjnie szukamy w tym zbiorze ${\displaystyle k}$-tego elementu, w przeciwnym przypadku rekurencyjnie szukamy w zbiorze ${\displaystyle A_{>}}$ elementu ${\displaystyle k-|A_{\leqslant }|}$ co do wielkości.

Złożoność czasowa

Pesymistyczna złożoność czasowa to ${\displaystyle O(n^{2}),}$ możemy bowiem (podobnie jak w QuickSorcie) wybierać cały czas do podziału największy element.

Równanie na oczekiwaną złożoność czasową w modelu permutacyjnym:

${\displaystyle f(n)={\begin{cases}0,&{\text{jeżeli }}n=1\\(n+1)+{\frac {1}{n}}(\sum _{j=1}^{n-k}f(n-j)+\sum _{j=n-k+2}^{n}f(j-1)),&{\text{wpp.}}\end{cases}}}$

Średnia złożoność jest liniowa.

Podany algorytm nie jest optymalny dla problemu selekcji, algorytm magicznych piątek działa pesymistycznie w czasie liniowym, więc jest znacząco lepszy.

Zobacz też

• algorytm magicznych piątek

Przypisy

Bibliografia

• Selekcja (materiały dydaktyczne MIMUW na studia informatyczne I stopnia).