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
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
Zarejestruj się i dołącz do największej społeczności programistów w Polsce.
Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.