3.3.4. Ordenación por mezcla y ordenación rápida.

• La ordenación por mezcla (mergesort) es un buen ejemplo de divide y vencerás. Para ordenar los elementos de un array de tamaño n:

  • Divide: el array original es dividido en dos trozos de tamaño igual (o lo más parecido posible), es decir ?n/2? y ?n/2?.
  • Resolver recursivamente los subproblemas de ordenar los dos trozos.
  • Caso base: si tenemos un solo elemento, entonces ya está ordenado.
  • Combina: combinar dos listas ordenadas. Se puede conseguir en O(n).

MergeSort (i, j: integer)

if pequeño(i, j) then

OrdenaciónDirecta(i, j)

else begin

s:= (i + j) div 2;

MergeSort(i, s);

MergeSort(s+1, j);

Combina (i, s, j);

end;

t(n) = t(?n/2?) + t(?n/2?) + f(n); Con f(n) ? O(n)

Suponiendo n potencia de 2, tenemos: t(n) = 2·t(n/2) + a·n + b

t(n) ? O(n·log n)

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica