Algorytm Hoare’a

Algorytm Hoare’a – algorytm rozwiązujący problem selekcji, czyli wyznaczający $k$-tą co do wielkości ($k$-tą statystykę pozycyjną) spośród danych $n$ liczb. Opiera się na pomyśle podobnym do algorytmu sortowania szybkiego, czyli na podziale zbioru na elementy mniejsze i większe od wybranego. Pomysłodawcą obu algorytmów jest Antony Hoare.

Działanie

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, gdyż 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).