Algorytmy i struktury danych/Selekcja

Definicja

Dany jest ciąg liczb $a[1,\dots ,n]$ oraz liczba $k$,

Należy wyznaczyć $k$-ty co do wielkości element tablicy $a[]$.

---

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
    
    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