Algorytm magicznych piątek

0

Witam
Poszukuję algorytmu tzw magicznych piątek. Jest to algorytm wyszukiwania k tego pod względem wielkości elementu w ciągu nieuporządkowanym. Jest to algorytm oparty na algorytmie Hoare'a rozwiązującym ten sam problem (jednak z gorszą szybkością).
Prosiłbym o jakąkolwiek przystępną formę zapisu tego algorytmu.
Pozdrawiam

0

moglby to ktos przetlumaczyc na c++ i najlepiej nie w pseudokodzie? gogluje i jakos nie moge tego <ort>znaleŹĆ</ort> ;/ ...

0
var
  a: array[1..5000000] of longint;
procedure sortuj(l, s: longint);
  var
    i, j, x: longint;
  begin
    for i := 1 to s - 1 do
    begin
      j := l + i;
      x := a[j];
      while (j > l) and (x < a[j - 1]) do
      begin
        a[j] := a[j - 1];
        dec(j);
      end;
      a[j] := x;
    end;
  end;
function medianofmedians(l, r: longint): longint;
  var
    i, p, x, m: longint;
  begin
    while l < r do
    begin
      i := l;
      p := l + 4;
      while p <= r do
      begin
        sortuj(p - 4, 5);
        x := a[i];
        a[i] := a[p - 2];
        a[p - 2] := x;
        inc(i);
        inc(p, 5);
      end;
      if p < r + 5 then
      begin
        if (r - l + 1) mod 5 > 1 then
          sortuj(p - 4, (r - l + 1) mod 5);
        x := a[i];
        a[i] := a[p - 4 + ((r - l) mod 5) div 2];
        a[p - 4 + ((r - l) mod 5) div 2] := x;
        inc(i);
      end;
      r := i - 1;
    end;
    medianofmedians := a[l];
  end;
var
  i, k, w, z, gl, gr, ll, lr, p, x, e, b: longint;
  f: boolean;
begin
  read(z);
  while z > 0 do
  begin
    read(w, k);
    for i := 1 to w do
      read(a[i]);
    f := false;
    gl := 1;
    gr := w;
    repeat
      ll := gl;
      lr := gr;
      x := medianofmedians(ll, lr);
      i := ll;
      p := 0;
      while i <= lr do
      begin
        b := a[i] - x;
        if b < 0 then
        begin
          a[ll] := a[i];
          inc(ll);
          inc(i);
        end
        else if b > 0 then
        begin
          e := a[i];
          a[i] := a[lr];
          a[lr] := e;
          dec(lr);
        end
        else
        begin
          inc(p);
          inc(i);
        end;
      end;
      f := (k >= ll) and (k <= lr);
      inc(ll, p);
      dec(lr, p);
      if ll > k then
        gr := lr
      else
        gl := ll;
    until f;
    writeln(x);
    dec(z);
  end;
end.

http://asd1.tcs.uj.edu.pl/docs/N.pdf

tyle, że to jest lomuto

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0