Quicksort

Quick sort é um algoritmo de ordenação com uma eficiência acima da média. É por esta razão que é muitas vezes preferido para efectuar a ordenação de um conjunto de elementos.

De seguida é apresentado uma implementação deste algoritmo em PHP, com as seguintes vantagens:

1. O primeiro elemento da chamada é a referência para o array, diminuindo assim a quantidade de memória requerida pelo algoritmo
2. A ordenação em feita inplace, sem o uso de arrays auxiliares
3. Parâmetro opcional para uma função de comparação para casos em que a ordenação não seja feita pela ordem natural os elementos do array, ou estes elementos não possuem essa ordem natural (como objectos)

/**
 * Função que implementa o quick sort sobre um array de elementos.
 *
 * @param $array   referência ao array a ser ordenado
 * @param $left    índice inferior do array/subarray a ser ordenado
 * @param $right   índice superior do array/subarray a ser ordenado
 * @param $ordfunc função opcional usada para comparar os elementos do array
 *
 * @return Booleano que dita se o array for ordenado (true) ou
 *         houve alguma validação de parâmetros que falhou (false).
 */
function quick_sort(&$array, $left, $right, $ordfunc = null)
{
    /* validação */
    if (!is_array($array) ||       // $array - tem de ser um array
        !is_int($left) ||          // $left  - tem de ser um numero inteiro
        $left < 0 ||               // $left  - não pode ser negativo
        $left >= count($array) ||  // $left  - tem de ser menor que o maior índice do array
        !is_int($right) ||         // $right - tem de ser um numero inteiro
        $right < 0 ||              // $right - não pode ser negativo
        $right >= count($right)) { // $right - tem de ser menor que o maior índice do array
        return false;
    }

    /* ignorar array com menos de 2 elementos */
    if ($right - $left < 1)
        return true;

    /* escolher o pivot : o último elemento */
    $pivot = $array[$right];

    /* inicialização do índice dos elementos menores que o pivot, este valor
     * representa o índice do próximo valor a ser inserido na lista de menores
     * que o pivot */
    $store = $left;

    /* ciclo de verificação do valor dos elemento do array/subarray em relação
     * ao pivot */
    for ($i = $left; $i < $right; $i++) {
        /* verificação de:
         * - se o parâmetro 'ordfunc' é uma função e o resultado desta for menor
         *   que zero
         * - ou se não for uma função, mas na comparação directa dos valores se
         *   verificar que o elemento iterado é menor que o valor do pivot */
        if ((is_callable($ordfunc) && $ordfunc($array[$i], $pivot) < 0) ||
             !is_callable($ordfunc) && $array[$i] < $pivot) {
            /* mover o elemento iterado para a lista de elementos menores
             * (para a posição apontada pela variável $store) */
            $aux = $array[$i];
            $array[$i] = $array[$store];
            $array[$store] = $aux;

            /* incrementar o índice do próximo elemento a ser inserido na lista
             * de valores menores que o pivot */
            $store++;
        }
    }

    /* colocar o pivot na sua posição, entre a lista de menores e a lista de
     * maiores, isto equivale ao valor do índice do próximo valor a ser inserido
     * na lsita de menores valores que o pivot */
    $aux = $array[$right];
    $array[$right] = $array[$store];
    $array[$store] = $aux;

    /* chamada recursiva da sub-lista antes da posição do pivot e da sub-list
     * pós a posição pivot, tanto uma como outra exclusivé */
    quick_sort($array, $left, $store - 1, $ordfunc);
    quick_sort($array, $store + 1, $right, $ordfunc);

    return true;
}

a chamada desta função poderá ser efectuada nos seguintes contornos:

/* lista de valores a serem ordenados */
$nums = array(4,6,7,8,9,1,2,3,4,8);

/* chamada da função de ordenação usando a ordem natural dos valores guardados
 * no array passado como parâmetro da função */
quick_sort($nums,
           0,
           count($nums) - 1);
print_r($nums);

/* chamada da função de ordenação usando uma função de comparação entre os
 * elementos a serem ordenados */
quick_sort($nums,
           0,
           count($nums) - 1,
           function ($a, $b) {
               return($b - $a); // menor que zero só se $a for menor que $b (ordem inversa)
           });
print_r($nums);

A este código poderia ser adicionado um método de escolha de um pivot para melhorar a performance da implementação. No entanto deixarei essa questão de optimização para curiosidade.