Ordenamiento Quicksort

Animación gráfica del ordenamiento quicksort. Fuente: Wikipedia

El algoritmo de ordenamiento de arreglos de un solo subíndice quicksort puede reducirse a dos pasos básicos:

1. Tome un elemento del arreglo –pivote– y ubique todos los valores mayores del lado derecho y los menores a la izquierda. Aquí hay un elemento ubicado en su posición apropiada y dos arreglos desordenados.
2. Usando recursividad realizar el paso 1 en cada uno de los arreglos desordenados.

Existen variantes según la elección del pivote. El siguiente código en C utiliza como pivote el elemento central del arreglo. Los valores dentro del arreglo son double -real-.

void quicksort (double a[], int primero, int ultimo)
{
    int i ,j, central, tmp;
    double pivote;

    central = (primero + ultimo)/2;
    pivote = a[central];
    i = primero;
    j = ultimo;

    do {
           while (a[i] < pivote)
            i++;
        while (a[j] > pivote)
            j–;
        if (i <= j)
        {
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i++;
            j–;
        }
    }while (i <= j);
    if (primero < j)
        quicksort(a, primero, j);
    if (i < ultimo)
        quicksort(a, i, ultimo);       
}