Algorytm Hoare’a – algorytm rozwiązujący problem selekcji, czyli wyznaczający -tą co do wielkości (-tą statystykę pozycyjną) spośród danych 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 zawierający liczb. Zadanie polega na wybraniu -tej co do wielkości. Wybieramy losową liczbę ze zbioru i dzielimy ten zbiór na elementy mniejsze lub równe od (zbiór ) oraz liczby większe od niej (zbiór ). Następnie, jeśli moc zbioru jest większa lub równa to rekurencyjnie szukamy w tym zbiorze -tego elementu, w przeciwnym przypadku rekurencyjnie szukamy w zbiorze elementu co do wielkości.
Złożoność czasowa Pesymistyczna złożoność czasowa to 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:
Ś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
Przypisy
Bibliografia Selekcja (materiały dydaktyczne MIMUW na studia informatyczne I stopnia).
Hoare