Batman caballero de la noche

2.7 ORDENACIÓN RÁPIDA DE HOARE (QUICKSORT)
Este método es probablemente el algoritmo de ordenación más utilizado, pues es
muy fácil de implementar, trabaja bien en casi todas las situaciones y consume en
general menos recursos (memoria y tiempo) que otros métodos.
Su diseño está basado en la técnica de Divide y Vencerás, que estudiaremos en
el siguiente capítulo, y consta de dospartes:
a) En primer lugar el vector a ordenar a[prim..ult] es dividido en dos subvectores
no vacíos a[prim..l–1] y a[l+1..ult], tal que todos los elementos del primero son
menores que los del segundo. El elemento de índice l se denomina pivote y se
calcula como parte del procedimiento de partición.
b) A continuación, los dos subvectores son ordenados mediante llamadas
recursivas aQuicksort. Como los subvectores se ordenan sobre ellos mismos, no
es necesario realizar ninguna operación de combinación.
Esto da lugar al siguiente procedimiento, que constituye la versión clásica del
algoritmo de ordenación rápida de Hoare: 68 TÉCNICAS DE DISEÑO DE ALGORITMOS
PROCEDURE Quicksort(VAR a:vector;prim,ult:CARDINAL);
VAR l:CARDINAL;
BEGIN
IF prim<ult THENl:=Pivote(a,a[prim],prim,ult);
Quicksort(a,prim,l-1);
Quicksort(a,l+1,ult)
END
END Quicksort;
La función Pivote parte del elemento pivote y permuta los elementos del vector
de forma que al finalizar la función, todos los elementos menores o iguales que el
pivote estén a su izquierda, y los elementos mayores que él a su derecha. Devuelve
la posición en la que ha quedado situado el pivotep:
PROCEDURE Pivote(VAR a:vector;p:INTEGER;prim,ult:CARDINAL)
:CARDINAL;
(* permuta los elementos de a[prim..ult] y devuelve una
posicion l tal que prim<=l<=ult, a[i]<=p si prim<=i<l,
a[l]=p, y a[i]>p si l<i<=ult, donde p es el valor inicial
de a[prim] *)
VAR i,l:CARDINAL;
BEGIN
i:=prim; l:=ult+1;
REPEAT INC(i) UNTIL(a[i]>p) OR (i>=ult);
REPEAT DEC(l) UNTIL (a[l]<=p);
WHILE i<l DO
Intercambia(a,i,l);
REPEAT INC(i) UNTIL (a[i]>p);
REPEAT DEC(l) UNTIL (a[l]<=p)
END;
Intercambia(a,prim,l);
RETURN l
END Pivote;
Este método es de orden de complejidad Θ(n
2
) en el peor caso y Θ(nlogn) en los
casos mejor y medio. Para ver su tiempo de ejecución, utilizando losmecanismos
expuestos en el primer capítulo, obtenemos la siguiente ecuación en recurrencia:
T(n) = 8 + T(a) + T(b) + TPivote(n)
donde a y b son los tamaños en los que la función Pivote divide al vector (por tanto
podemos tomar que a + b = n), y TPivote(n) es la función que define el tiempo de
ejecución de la función Pivote.
El procedimiento Quicksort “rompe” la filosofía de caso mejor, peor ymedio de
los algoritmos clásicos de ordenación, pues aquí tales casos no dependen de la
ordenación inicial del vector, sino de la elección del pivote. ORDENACIÓN 69
Así, el mejor caso ocurre cuando a = b = n/2 en todas las invocaciones
recursivas del procedimiento, pues en este caso obtenemos TPivote(n) = 13 + 4n, y
por tanto:
T(n) = 21 + 4n + 2T(n/2).
Resolviendo estaecuación en recurrencia y teniendo en cuenta las condiciones
iniciales T(0) = 1 y T(1) = 27 se obtiene la expresión final de T(n), en este caso:
T(n) = 15nlogn + 26n +1.
Ahora bien, si a = 0 y b = n–1 (o viceversa) en todas las invocaciones recursivas
del procedimiento, TPivote(n) = 11 + 39/8n, obteniendo:
T(n) = 19 + 39/8n + T(n–1).
Resolviendo la ecuación para las mismas condicionesiniciales, nos
encontramos con una desagradable sorpresa:
T(n) = 1 ( )
8
213
8
3 2 2
n + n + ∈Θ n .
En consecuencia, la elección idónea para el pivote es la mediana del vector en
cada etapa, lo que ocurre es que encontrarla requiere un tiempo extra que hace que
el algoritmo se vuelva más ineficiente en la mayoría de los casos (ver problema
2.15). Por esa razón como pivote suele...