Curso de C
Ordenação com o Quick Sort
Você está em: MarMSX >> Cursos >> C
O Quick Sort é um algoritmo de ordenação rápido, criado por C.A.R. Hoare na década de 60. Ele adota a estratégia de divisão e conquista.
A estratégia consiste em rearranjar as chaves de modo que as chaves menores precedam as chaves maiores. Em seguida, o quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada.
Passos:
- Escolha um elemento da lista, denominado pivô.
- Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sub listas não ordenadas.
- Recursivamente ordene a sub lista dos elementos menores e a sub lista dos elementos maiores.
Fonte: Wikipedia[1]
A seguir, será apresentado o algoritmo que realiza o Quick Sort em C. Ele possui um atributo "asc" que indica se é feito da forma crescente (asc=1) ou decrescente (asc<>1).
#include <stdio.h>
int v[10] = {7, 8, 1, 4, 5, 9, 0, 3, 2, 6};
int partition(int lo, int hi, int asc)
{
int i, j, pivot, aux;
int flag=1;
pivot = v[(hi + lo)/2];
i = lo-1;
j = hi+1;
while (flag==1)
{
if (asc)
{
do
{
i=i+1;
} while (v[i] < pivot);
do
{
j=j-1;
} while (v[j] > pivot);
}
else
{
do
{
i=i+1;
} while (v[i] > pivot);
do
{
j=j-1;
} while (v[j] < pivot);
}
if (i>=j)
return j;
aux = v[i];
v[i] = v[j];
v[j] = aux;
}
}
void quicksort(int lo, int hi, int asc)
{
int p;
if (lo>=hi)
return;
p = partition(lo, hi, asc);
quicksort(lo, p, asc);
quicksort(p+1, hi, asc);
}
void print()
{
int i;
for (i=0; i<10; i++)
printf("%d ",v[i]);
printf("\n");
}
main()
{
printf("Vetor inicial: ");
print();
quicksort(0,9,1);
printf("Vetor final: ");
print();
}
Adaptado de: [1] por MarMSX.
Agora iremos fazer um teste para ver o tempo gasto pelo MSX para ordenar um vetor com 10.000 posições com o Quick Sort.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int v[10000];
int t;
int partition(int lo, int hi)
{
int i, j, pivot, aux;
int flag=1;
pivot = v[(hi + lo)/2];
i = lo-1;
j = hi+1;
while (flag==1)
{
do
{
i=i+1;
} while (v[i] < pivot);
do
{
j=j-1;
} while (v[j] > pivot);
if (i>=j)
return j;
aux = v[i];
v[i] = v[j];
v[j] = aux;
}
}
void quicksort(int lo, int hi)
{
int p;
if (lo>=hi)
return;
p = partition(lo, hi);
quicksort(lo, p);
quicksort(p+1, hi);
}
void createRandArray()
{
int i;
srand(time(NULL));
for (i=0; i<10000; i++)
v[i] = (int) rand()%5000 + 1;
}
main()
{
printf("Criando vetor aleatorio de 10.000 posicoes ...\n");
createRandArray();
printf("Ordenando ...\n");
t = time(NULL);
quicksort(0,9999);
t = time(NULL) - t;
printf("Tempo gasto: %d segundos.\n", t);
}
O MSX levou cerca de 38 segundos para ordenar 10.000 posições.
Obs: compilar utilizando o Hitech-C, no qual o patch "time.obj" foi adicionado para o rand() e o time() funcionar corretamente.
Referências:
[1]- Quick Sort, Wikipedia - http://en.wikipedia.org/wiki/Quicksort