Para continuar nosso estudo sobre complexidade, consideremos o problema de ordenar um vetor, i.e. dado o vetor v(1:n), não ordenado, produzir o vetor w(1:n) contendo os mesmos elementos de v |
w(1) <= w(2) <= ... <= w(n).

function w= bubbles(v)
%*** alg da bolha para ordenacao ***
n = length(v)
for i=2:n

j=i;
vj=v(j);
vjm=v(j-1)
while( j>1 & vj>vjm )

v(j)=vjm;
v(j-1)=vj;
j=j-1;
vj=v(j);
vjm=v(j-1);
end

end
w=v;
%*************************************

function x = merge(v,w)
% merge( , ) junta os elementos de dois vetores
% v e w ja ordenados, em um novo vetor ordenado x
nv = length(v);
nw = length(w);
nx = nv+nw;
x = zeros(1,nx);
jv=1; jw=1; jx=1;
while ( jx <= nx )

if ( jv > nv )

x(jx) = w(jw);
jw = jw+1;
jx = jx+1;

elseif ( jw > nw )

x(jx) = v(jv);
jv = jv+1;
jx = jx+1;

elseif ( v(jv) <= w(jw) )

x(jx) = v(jv);
jv = jv+1;
jx = jx+1;

else

x(jx) = w(jw);
jw = jw+1;
jx = jx+1;

end

end
%****************************

1. Use a funcão merge como base para um algoritmo de ordenação tipo divida-e-conquiste recursivamente com complexidade c(n) = O(n*log₂(n)).
   
2. Implemente-o como uma função w = mergesr(v).
   
3. Dê uma versão iterativa mergesi(v). Use as linguagens Matlab, Scilab, QBasic ou C.
   
4. Mostre que a complexidade da ordenação pelo algoritmo bolha é (no Pior Caso) da ordem de n².
   Mostre que no Melhor Caso (j previamente ordenado) bubbles(v) tem complexidade O(n).
   
5. Faça experimentos computacionais para "medir" a complexidade esperada da função bubbles( ), i.e. E(c(n)) para um argumento v aleatório da forma
   u=1:n, r=rand(1,n), v=a*u+r, a em [-1,1].