Algoritmo de ordenamiento QuickSort

Artículo perteneciente a la sección de algoritmos

Hola a todos,

Si habéis seguido la sección de algoritmos habréis visto ya los algoritmo más fáciles de implementar e ineficientes. Ahora le toca el turno a un algoritmo que es de lo más eficientes que existen sin tener un complejidad excesiva, el algoritmo QuickSort.

Este algoritmo se basa en la teoría de divide y vencerás. Parte el vector a ordenar en dos trozos, en la parte más baja pone los números más bajos y en la parte más alta los números más altos. Después se aplica el mismo procedimiento a cada una de las partes de forma recursiva hasta que no se puede dividir más... en ese momento el vector ya está ordenado.

El problema de este algoritmo más allá de su implementación (que ya veréis que tampoco es tan compleja) es la elección del valor (llamado pivote) que se usa para dividir cada una de las listas. Si el pivote está justo en el medio de la lista, el rendimiento es óptimo, si el pivote está a un extremo de los valores de esa subsección el rendimiento es parecido al del algoritmo de burbuja, el problema es que no es fácil encontrar ese valor. Para lo que nos interesa aquí ( que aprendáis el algoritmo) no nos hace falta decir más, si estáis interesados comentadlo y tal vez me expanda un poco más la explicación.

El código de este algoritmo es el siguiente:

int LPVector::distribuir(int b, int t)
{
    int i;
    int pivote, valor_pivote;
    int temp;

    pivote = b;
    valor_pivote = v[pivote];

    for (i=b+1; i<=t; i++)
{
        if (v[i] < valor_pivote)
{
           pivote++;
           temp=v[i];
           v[i]=v[pivote];
           v[pivote]=temp;
}
    }
    temp=v[b];
    v[b]=v[pivote];
    v[pivote]=temp;
return pivote;
}

void LPVector::RecursiveQuicksort(int b, int t)
{
int pivote;
    if(b < t)
{
pivote=distribuir(b, t);
        RecursiveQuicksort(b, pivote-1);
        RecursiveQuicksort(pivote+1, t);
    }
}

void LPVector::QuickSort(void)
{
RecursiveQuicksort(0,n-1);
}

Espero que os haya servido y hayáis aprendido un poco más sobre los algoritmos de ordenación.

En breve comenzaré con las comparativas entre algoritmos y las implementaciones en asm

Nos vemos