/*!
 * \file        quicksort.c
 * \brief       Módulo com o algoritmo quicksort.
 *
 * \date        29/05/2012
 * \version     0.0.1
 * \author      Alessandro Elias, ae11@inf.ufpr.br
 * \author      Ruanito Diego Santos, rds@inf.ufpr.br
 */

/*!
 * Método de ordenação quicksort.
 *
 * \param   [in, out] array[] - vetor desordenado.
 * \param   [in] first - índice do primeiro elemento de array[].
 * \param   [in] last - índice do último elemento de array[].
 * \param   [out] ncomp - número de comparações feitas para ordenar array[].
 * \param   [out] nperm - número de permutações feitas para ordenar array[].
 *
 * \remarks O pivô não é o melhor, pois estamos pegando o elemento que se
*           encontra no meio do vetor. As técnicas utilizadas serão implementas
*           futuramente.
 */
void quick_sort(int array[], int first, int last, int *ncomp, int* nperm)
{
    int temp, low, high, list_separator;

    low = first;
    high = last;
    list_separator = array[(first + last) / 2];
    do {
        while( array[low] < list_separator ) {
            low++;
            (*ncomp)++;
        }
        while( array[high] > list_separator ) {
            high--;
            (*ncomp)++;
        }
        if( low <= high ) {
            temp = array[low];
            array[low++] = array[high];
            array[high--] = temp;
            (*nperm)++;
        }
    } while( low <= high );
    
    if( first < high )
        quick_sort(array, first, high, ncomp, nperm);
    if( low < last )
        quick_sort(array, low, last, ncomp, nperm);
}/* quick_sort */