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)<br />
{<br />
   int i, j, meio, aux;</p>
<p>   i = inicio;<br />
   j = fim;<br />
   meio = vetor[(inicio + fim) / 2];</p>
<p>   do<br />
   {<br />
      while(vetor[i] &lt; meio)<br />
         i++;<br />
      while(vetor[j] &gt; meio)<br />
         j--;<br />
      if(i &lt;= j)<br />
      {<br />
         aux = vetor[i];<br />
         vetor[i] = vetor[j];<br />
         vetor[j] = aux;<br />
         i++;<br />
         j--;<br />
      }<br />
   }while(i &lt;= j);</p>
<p>   if(inicio &lt; j)<br />
      quickSort(vetor, inicio, j);<br />
   if(i &lt; fim)<br />
      quickSort(vetor, i, fim);<br />
}