Curso de C
Ordenação com o Quick Sort


  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:
  1. Escolha um elemento da lista, denominado pivô.
  2. 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.
  3. 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

<< Anterior Linguagem C Próxima >>


/MARMSX/CURSOS/C