Ordenamiento por Quicksort

 

Considerado uno de los mejores métodos de ordenamiento, se le atribuye su creación a C.A. R. Hoare (1962).

La idea básica del método Quicksort es la siguiente:

1. Se selecciona una llave en particular de la lista. Esta llave se puede escoger aleatoriamente o haciendo la media de un pequeño conjunto de llaves tomados de la lista. El valor óptimo sería aquél que esté precisamente en medio del rango de valores. Esto se hace para evitar el peor caso de Quicksort, que es seleccionar una llave del extremo. No obstante, incluso en el peor de los casos Quicksort funciona correctamente.

2. Se divide la lista en dos partes, una con todos los elementos menores o iguales que la llave seleccionada y otra con todos los elementos mayores o iguales.

3. Se repiten los puntos 1 y 2 para cada parte restante hasta que la lista esté ordenada.

El proceso descrito es esencialmente recursivo.

Veamos ahora un ejemplo práctico de cómo funciona este método de ordenamiento: consideremos la siguiente lista de elementos:

7 – 5 – 3 – 8 – 9 – 10 – 14 – 6 – 4 – 1

Supongamos que el elemento que se seleccionó al azar fue el 8, entonces nuestra lista se divide en dos partes, una con los mayores y una con los menores que el 8.

Si trabajamos con L1, supongamos que seleccionamos el elemento 4 al azar, entonces nuestra lista se divide en dos partes, una con los mayores y una con los menores que el 4.

Así sucesivamente hasta que se llega a una lista con dos elementos, los cuales se comparan y se retornan en orden.

Lo mismo sucede con la L2 del comienzo (L2: 9 – 10 – 14), hasta que se obtienen la lista con dos elementos los cuales se ordenan y se retornan.

Al finalizar, ambas listas estarán ordenadas (tanto la que tenía los mayores como la que tenía los menores que la llave seleccionada) y la lista completa estará ordenada.

Análisis de Rendimiento:

El primer paso se ve de la siguiente forma:

El segundo paso:

Procesar la sublista 1 requiere aproximadamente comparaciones, lo mismo que para procesar la lista 2. De hecho, el proceso de cada superpaso requiere O(n) comparaciones.

En promedio se requieren superpasos para clasificar la lista completa. Luego el método de Quicksort requiere de un promedio de comparaciones. Este es el mejor desempeño encontrado hasta aquí en una técnica de ordenamiento; recordemos que los métodos lineales requieren todos de O(n^2) comparaciones.

Una implementación de este método de ordenamiento puede ser la siguiente:

void qs(Lista Numeros, int inf, int sup)
{
    int izq=inf, der=sup, mitad, x;
    mitad=Numeros[(izq+der)/2];
    do{
        while((Numeros[izq]<mitad)&&(izq<sup))izq++;
        while((mitad<Numeros[der])&&(der>inf))der–;
        if(izq<=der)
        {
            x=Numeros[izq], Numeros[izq]=Numeros[der], Numeros[der]=x;
            izq++;
            der–;
        };
    }while(izq<=der);
    if(inf<der) qs(Numeros,inf,der);
    if(izq<sup) qs(Numeros,izq,sup);
};

void QuickSort(Lista Numeros, int n)
{
    qs(Numeros,0,n-1);
};

Cómo podrá apreciarse, este algoritmo selecciona el elemento medio de la lista de claves, ya que como se dijo anteriormente se trata de un número al azar. Lamentablemente, éste no considera el peor caso, pues puede darse el caso que el elemento medio sea exactamente un valor extremo de la lista, pero eso es un punto fácil de solucionar. A pesar de todo, esta implementación funciona bastante bien.