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 Hoar'a

• opis algorytmu,
• analiza (optymistyczna, pesymistyczna)
• kod programu z implementacją

Przykładowa implementacja:

function AlgHoara(A[1..n],k);
begin
  if n=1 && k=1 then' return A[1];
  m:=A[1]; l:=1; r:=n;
  // parition
  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;
    
  if (r<=k) then 
    return AlgHoara(A[1..r],k)
  else
    return AlgHoara(A[r+1..n],k-r)
end;

Algorytm magicznych piątek

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

Plan:

• algorytm Hoare'a
• algorytm magicznych piątek

---

powrót do wykładu