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_{⩽}$) oraz liczby większe od niej (zbiór $A_{>}$). Następnie, jeśli moc zbioru $A_{⩽}$ 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_{⩽}|$ 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{array}{cc}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{array}$

Ś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).