Algorytmy i struktury danych/Selekcja

Rozważmy następujący problem:

Dany jest zbiór $A$ składający się $n$ liczb oraz liczba $k$.
Należy wyznaczyć $k$-ty co do wielkości element zbioru $A$.

Dla niektórych wartości $k$ (np. 1 lub n) problem jest bardzo prosty i wymaga jedynie wyznaczenia minimalnej lub maksymalnej wartości, co możemy zrobić w czasie $O(n)$.

Najprostszym rozwiązaniem naszego problemu, może być uporządkowanie zbioru, np. algorytmem MergeSort i zwrócenie k-tego elementu. Takie postępowanie wymaga czasu $O(n\log n)$.

Jednak można łatwo zauważyć, że nasz problem jest znacznie prostszy od problemu sortowania. Czy można rozwiązać go szybciej? Okazuje się, że jest to możliwe, w następnej części wykładu przedstawimy dwa algorytmy, które rozwiązują nasz problem znacznie sprytniej.

---

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 pierszej części tablicy: A[1..r] zostają przeniesione elementy o wartościach mniejszych lub równych m. W 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ń rekrurencyjnych (jak to było w przypadku algorytmu QuickSort), wykonać jedynie jedno wywołanie rekurencyjne.

Jeśli k<=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

function AlgHoara(A[1..n],k);
begin
  if n=1 && k=1 then return A[1];

  // Partition
  m:=A[1]; l:=1; r:=n;
  while(l<r) do begin
    while (l<n && A[l]<m) do l++;
    while (r>1 && A[r]>m) do r--;
    if (l<=r) then begin
      tmp:=A[l]; A[l]:=A[r]; A[r]:=tmp;
      l++; r--;
    end;
  end;

  // TODO, sprawdzić czy nie ma błędów     
  if (r<=k) then 
    return AlgHoara(A[1..r],k)
  else
    return AlgHoara(A[r+1..n],k-r)
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).

• TODO -- dodać kod programu z implementacją

Algorytm magicznych piątek

• opis algorytmu,
• analiza,
• kod programu z implementacją

Plan:

• algorytm Hoare'a
• algorytm magicznych piątek

---

powrót do wykładu