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

• La ordenación rápida (quicksort) utiliza también la técnica divide y vencerás.

  • Divide: el array (i..j) es dividido usando un procedimiento Pivote, que devuelve un entero l entre (i, j), tal que A[ia] ? A[l] ? A[ja], para ia = i..l-1, ja=l+1..j.
  • Ordenar recursivamente los trozos (i..l-1) y (l+1..j).
  • Caso base: si tenemos un solo elemento, entonces ya está ordenado.
  • Combina: no es necesario realizar ninguna operación.

QuickSort (i, j: integer)

if i ? j then

{ Ya está ordenado }

else begin

Pivote (i, j, l);

QuickSort (i, l-1);

QuickSort (l+1, j);

end;

• Aunque no hay coste de combinar los resultados, la llamada a Pivote tiene un coste O(n).

• Las particiones no tienen porqué ser de tamaño n/2.

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica