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

Pivote (i, j: integer; var l: integer)

var p: tipo; { p es el pivote }

k, l: integer;

begin

p:= A[i];

k:= i;

l:= j+1;

repeat k:= k+1 until (A[k] > p) or (k ? j);

repeat l:= l-1 until (A[l] ? p);

while k < l do begin

intercambiar (k, l);

repeat k:= k+1 until (A[k] > p);

repeat l:= l-1 until (A[l] ? p);

end;

Intercambiar (i, l);

end;

• Tiempo de ejecución: Mejor caso.

Todas las particiones son de tamaño similar, n/2.

t(n) = 2·t(n/2) + b·n + c ? ?(n·log n)

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica