Skuska 30.5.2007
1.
MFFSORT(A,i,j)
{
if (A[i] > A[j]) swap (A[i], A[j]);
if (i + 1 < j)
{
k = spodna_cela_cast(j – i + 1);
MFFSORT(A, i, j – k);
MFFSORT(A, i + k, j);
MFFSORT(A, i, j – k);
}
}
Dokazte alebo vyvratte: alg. utriedi dane pole A
2.
Urcte zlozitost alg. z (1.)
3.
na vstupe [x_i, y_i],(i = 1..n) su bunky gridu p x p
2 bunky su susedne, ak |x_1 – x_2| <= 1 && |y_1 – y_2| <=1
Napiste alg, ktory uci v O(n) ci vstup obsahuje susedne bunky.
Mozte si alokovat pole velkosti O(n)