QUICKSORT

El algoritmo quick sort se basa en la estrategia divide-y-vencerás, porque divide el problema en dos subproblemas, que se resuelven de manera individual e independiente. Los resultados se unen después. Dado un conjunto de números a1, a2,..., an, se escoge un elemento X para dividir dicho conjunto en dos listas, como se muestra a continuación:

Después de la división, el quick sort puede aplicarse en forma recursiva tanto a L1 como a L2, con lo cual se obtiene una lista ordenada, ya que L1 contiene a todos los a¡ menores que o iguales a X y L2 contiene a todos los ai mayores que X.
El problema es ¿cómo dividir la lista original? Ciertamente, no debe usarse X para recorrer toda la lista y decidir si un a¡ es menor que o igual a X. Hacer lo anterior provoca una gran cantidad de intercambio de datos. Sino que se utilizan dos apuntadores que se mueven al centro y realizan intercambios de datos según sea necesario. El algoritmo es:

Quicksort(arreglo a, int f, int l)

{

if (f>l) return;

int X = af;

int i=f+1;

int j=l;

do

{

while((aj >= X) && (j>=f+1))

j = j-1;

while((ai<= X) && (i<=f+l))

i=i+1;

if(i<j){

int aux;

ai = aj;

aj = aux;}

}while(i<j)

Quicksort(a, f, j-1);

Quicksort(a, j+1, l);

}

El siguiente ejemplo, ilustra el algoritmo:

El mejor caso de quick sort ocurre cuando X divide la lista justo en el centro. Es decir, X produce dos sublistas que contienen el mismo número de elementos. En este caso, la primera ronda requiere n pasos para dividir la lista original en dos listas. Para la ronda siguiente, para cada sublista, de nuevo se necesitan n/2 pasos (ignorando el elemento usado para la división). En consecuencia, para la segunda ronda nuevamente se requieren 2 • (n/2) = n pasos. Si se supone que n = 2^P, entonces en total se requieren p*n pasos. Sin embargo, p = log2 n. Así, para el mejor caso, la complejidad temporal del quick sort es O(n log n).

El peor caso del quick sort ocurre cuando los datos de entrada están ya ordenados o inversamente ordenados. En estos casos, todo el tiempo simplemente se está seleccionando el extremo (ya sea el mayor o el menor). Por lo tanto, el número total de pasos que se requiere en el quick sort para el peor caso es:

n + (n - 1) + ••• + 1 = n/2 (n + 1) = O(n^2).

Para analizar el caso promedio, sea T(n) que denota el número de pasos necesarios para llevar a cabo el quick sort en el caso promedio para n elementos. Se supondrá que después de la operación de división la lista se ha dividido en dos sublistas. La primera de ellas contiene s elementos y la segunda contiene (n - s) elementos. El valor de s varía desde 1 hasta n y es necesario tomar en consideración todos los casos posibles a fin de obtener el desempeño del caso promedio. Para obtener T(n) es posible aplicar la siguiente fórmula:

T(n) = Promedio(T(s) + T(n - s)) + cn con l<=s<=n

donde cn denota el número de operaciones necesario para efectuar la primera operación de división. (Cada elemento es analizado antes de dividir en dos sublistas la lista original). Al resolver matemáticamente, se obtiene una eficiencia O(n log n).

De igual manera, se procede para hacer un análisis al algoritmo de Mergesort.

Ejercicio:

Demuestre que en quick sort, la pila máxima necesaria es O(log n).