PrEDA: el algoritmo de ordenamiento Quicksort

Vuelvo a la carga con los algoritmos de programación. Hoy traigo a modo de code-kata el algoritmo de ordenamiento Quicksort. En este algoritmo se utiliza la estrategia de programación divide y vencerás. Aplicándola, vamos dividiendo un vector inicial no ordenado, en subvectores que vamos a dividir una y otra vez recursivamente, hasta tener todos los elementos ordenados.

Antes de dividir un vector en dos subvectores se aplica una técnica de pivotaje. Con este pivotaje de los elementos, obtendremos el vector dividido en 2 partes, más un elemento central llamado pivote. Este elemento pivote hará que en la parte izquierda del vector todos los elementos sean menores que el pivote. Y a su vez, en la parte derecha, todos los elementos serán mayores que el pivote.

Un poco de teoría

Después de la división del vector en subvectores más sencillos de ordenar, hay que volver uniéndo las soluciones resultantes. Esto es el proceso normal de división y después fusión de las respuestas de la estrategia de divide y vencerás.

Queda definir más el proceso de pivotaje previo a la división del vector en dos subvectores. Este proceso de pivotaje, y la técnica de división está muy bien explicado aquí: https://es.wikipedia.org/wiki/Quicksort

Dicho esto, sólo queda ir al grano a ver el código fuente..

Preparando los datos

<?php

define('SIZE_OF_ARRAY', 30);
define('TRACE', true);
define('WAIT_TIME', 0);

$theArray = array();
for ($i = 0; $i < SIZE_OF_ARRAY; ++$i) {
    $theArray[$i] = rand(0, 9);
}

$initialArray = $theArray;
$theArray = quicksort($theArray);
echo 'Initial array: '.implode('-', $initialArray).PHP_EOL;
echo 'Final array: '.implode('-', $theArray).PHP_EOL;

El algoritmo principal de Quicksort

function quicksort($theArray)
{
    printToScreen('>> quicksorting', $theArray, '');

    $positionPivot = 0;
    if (count($theArray) <= 1) {
        return $theArray;
    } else {
        pivoting($theArray, $positionPivot);

        printToScreen('>> after pivoting', $theArray, 'pivot='.$positionPivot);

        $nItems1 = $positionPivot;
        $array1 = quicksort(array_slice($theArray, 0, $nItems1));
        $nItems2 = count($theArray) - $positionPivot - 1;
        $array2 = quicksort(array_slice($theArray, $positionPivot + 1, $nItems2));

        return array_merge($array1, array($theArray[$positionPivot]), $array2);
    }
}

He marcado en negrita el kit de la cuestión. Al ser un algoritmo con estrategia de divide y vencerás, tenemos que subdividir el problema grande en subproblemas más fácilemente resolubles. Para esto el pivotaje y las dos llamadas recursivas. Luego en el return se unen los resultados que ya serán vectores ordenados.

La función de pivotaje

Para elemento pivote en este caso se elije el primer elemento:

function pivoting(&$theArray, &$positionPivot)
{
    $p = $theArray[0];

    printToScreen('>> pivoting', $theArray, 'using pivot [0]='.$p);

    $k = 0;
    $l = count($theArray);

    do {
        ++$k;
    } while (!($theArray[$k] > $p or $k >= count($theArray) - 1));
    do {
        --$l;
    } while (!($theArray[$l] <= $p));

    while ($k < $l) {
        // interchange
        $aux = $theArray[$k];
        $theArray[$k] = $theArray[$l];
        $theArray[$l] = $aux;

        printToScreen('>> pivoting', $theArray, 'changed ['.$k.'] with ['.$l.']');

        do {
            ++$k;
        } while (!($theArray[$k] > $p));
        do {
            --$l;
        } while (!($theArray[$l] <= $p));
    }

    // interchange
    $aux = $theArray[0];
    $theArray[0] = $theArray[$l];
    $theArray[$l] = $aux;

    printToScreen('>> pivoting', $theArray, 'changed [0] with ['.$l.']');

    $positionPivot = $l;
}

Una función auxiliar

Para ir imprimiendo los datos por pantalla, dejo esta función:

function printToScreen($preStr, $theArray, $postStr)
{
    echo str_pad($preStr, 20, ' ');
    foreach ($theArray as $item) {
        echo str_pad($item, 3, ' ');
    }
    echo $postStr.PHP_EOL;
    sleep(WAIT_TIME);
}

Terminando

Si todo va bien se puede ejecutar poniendo todo este código en un fichero .php y ejecutándolo desde línea de comandos verás algo parecido a esto: