Algoritmos de Ordenação #5 – Quick Sort

Padrão


Temos aqui, um dos mais rápidos algoritmos de ordenação, o Quick Sort (rápido até no nome!). Grande parte da sua eficiência, dá-se pelo fato de utilizar técnicas de recursão (uma função que faz uma chamada a ela mesma). Com isso, este é considerado um algoritmo complexo. Nesta minha implementação, é necessário passar-se o conjunto de dados e o início e fim (no caso, início 0 e fim tamanho – 1).

Segue a implementação do algoritmo em C:

void quickSort(int *vetor, int inicio, int fim)
{
   int i, j, meio, aux;

   i = inicio;
   j = fim;
   meio = vetor[(inicio + fim) / 2];

   do
   {
      while(vetor[i] < meio)
         i++;
      while(vetor[j] > meio)
         j--;
      if(i <= j)
      {
         aux = vetor[i];
         vetor[i] = vetor[j];
         vetor[j] = aux;
         i++;
         j--;
      }
   }while(i <= j);

   if(inicio < j)
      quickSort(vetor, inicio, j);
   if(i < fim)
      quickSort(vetor, i, fim);
}


Deixe uma resposta