Algorytm Hoare’a

Algorytm Hoare’a – prosty algorytm rozwiązujący problem selekcji. Problem selekcji polega na wyznaczeniu $k$-tej co do wielkości wśród $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 $A$ zawierający $n$ liczb. Zadanie polega na wybraniu $k$-tej co do wielkości. Wybieramy losową liczbę $l$ ze zbioru $A$ i dzielimy ten zbiór na elementy mniejsze lub równe od $l$ (zbiór $A_{\leqslant }$) oraz liczby większe od niej (zbiór $A_{>}$). Następnie, jeśli moc zbioru $A_{\leqslant }$ jest większa lub równa $k,$ to rekurencyjnie szukamy w tym zbiorze $k$-tego elementu, w przeciwnym przypadku rekurencyjnie szukamy w zbiorze $A_{>}$ elementu $k-|A_{\leqslant }|$ co do wielkości.

Złożoność czasowa

Pesymistyczna złożoność czasowa to $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:

$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

Bibliografia

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