Algorytm Hoare'a

Algorytm jest oparty na tym samym pomyśle, co algorytm sortowania QuickSort.

Dla danej tablicy A[1..n] oraz liczby k, algorytm wybiera element dzielący m (np. pierwszy element z tablicy), a następnie używa go do podzielenia tablicy na dwie części. Do pierwszej części tablicy - A[1..r] - zostają przeniesione elementy o wartościach mniejszych lub równych m. Do drugiej części (A[r+1..n]) - elementy o wartościach większych lub równych m.

Ponieważ naszym zadaniem jest jedynie wyznaczenie k-tego co do wielkości elementu tablicy, możemy zamiast 2 wywołań rekurencyjnych (jak to było w przypadku algorytmu QuickSort) wykonać tylko jedno wywołanie rekurencyjne.

Jeśli \( k\le r \), to poszukiwana wartość znajduje się w pierwszej części tablicy, wpp. możemy zawęzić poszukiwania do drugiej części tablicy, jednak zamiast wyszukiwać k-tej wartości musimy poszukiwać (k-r)-tej wartości.

Algorytm Hoare'a

function AlgHoara(A[1..n],k); 
begin 
  if n=1 and k=1 then return A[1]; 
  // Partition 
  m:=A[1]; l:=1; r:=n; 
  while(l<r) do begin 
    while (A[l]<m) do l++; 
    while (m<A[r]) do r--; 
    if (l <=r) then begin 
      tmp:=A[l]; A[l]:=A[r]; A[r]:=tmp; 
      l++; r--; 
    end; 
  end; 
  if (k<=r) then 
    return AlgHoara(A[1..r],k) 
  else 
    return AlgHoara(A[r+1..n],k-r) 18 
end;

Analiza algorytmu

Niestety, w pesymistycznym przypadku ten algorytm może zachowywać się bardzo źle. Dla uporządkowanego ciągu i k=n czas działania algorytmu wynosi \( O(n^2) \). Jednak tak jak w przypadku algorytmu QuickSort, w średni koszt działania algorytmu jest znacznie lepszy i wynosi O(n).