Ordenando elementos com qsort() – C/C++

Ja havia escrito um tutorial sobre como ordenar elementos usando C/C++ mas usando a teoria por trás da implementação e demonstrando 3 dos diferentes métodos. Dessa vez resolvi escrever esse tutorial para mostrar uma função bastante conhecida (ou não) da linguagem C/C++, estou falando da função qsort(). Essa funcao faz parte da biblioteca stdlib.h.

Exemplo de uso: qsort (vetor, numero_de_elementos, sizeof(vetor), comparador);

O parâmetro comparador passado para esta função é o nome da função que irá determinar o critério de comparação.

Essa função utiliza a teoria do método de ordenação QuickSort que atualmente é um dos métodos mais rápidos e eficientes no meio da programação para ordenação de elementos. Para quem quiser saber um pouco mais sobre o método e implementações do mesmo poderá acessar os links abaixo:

LINK1        LINK2        LINK3

Esse algoritmo foi testado em um notebook HP-G42 com 2 GB de memoria DDR3 e com processador dual core T4500 de 2.30GHZ. O numero máximo de valores utilizados foi de 100.000.000. O sistema operacional foi Ubuntu 10.10 com a versão de kernel 2.6.35-30. Foi compilado com o gcc em linha de comando. A versão do gcc era 4.4.5.

O funcionamento básico do algoritmo é:

– Aloca memoria para o numero definido por TAM que é igual a 100.000.000
– Gera os valores randomicamente e armazena em um vetor que foi alocado
inicialmente, armazena os valores em um arquivo texto para uma possível conferencia.
– Chama uma função de tempo que pega a hora corrente do sistema.
– Chama a função de ordenação qsort() passando o vetor alocado com os valores .
– Chama a função tempo novamente após a ordenação dos elementos.
– Calcula a diferença entre o primeiro tempo e o segundo tempo.
– Escreve os valores ordenados em um arquivo texto para que possa ser conferido.
– Libera a memoria alocada inicialmente.
– Mostra o tempo total de execução na tela.

/*********************************
Autor: Fernando Krein Pinheiro
Data: 06/06/2010
Linguagem: C
========= IMPORTANTE ===========
O código esta livre para usar,
citar e compartilhar desde que
mantida sua fonte e seu autor.
Obrigado.
*********************************
Se voce estiver usando windows
mude a funcao do tempo para esta :

tempo = ((double)(fim-inicio))/CLK_TCK;
*/
//###################################################################

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TAM 100000000

//###################################################################
int comparador(valor1, valor2)
{
    if ( *(int*)valor1 > *(int*)valor2 )
    {
    	return 1;
    }
    else
    	if( *(int*)valor1 == *(int*)valor2 )
    	{
            return 0;
	}
    	else
		if ( *(int*)valor1 < *(int*)valor2 )
		{
           	      return -1;
		}
}
//##################################################################
int main()
{
	clock_t inicio,fim;
	int *vetor, indice;
	double tempo = 0;
	FILE *arquivo;

	vetor = (int *) malloc(sizeof(int)*TAM);
	srand(time(NULL));

	arquivo = fopen("Desordenados.txt","w");
	if(!arquivo)
	{
		printf("Arquivo nao pode ser criado");
	}
		for (indice = 0; indice < TAM; indice++)
		{
    			vetor[indice] = rand() % TAM;
    			fprintf(arquivo,"%d\n",vetor[indice]);
		}

		fclose(arquivo);
		inicio=clock();
		qsort(vetor, (size_t)TAM, sizeof(int), comparador );
		fim=clock();
		tempo = (double)(((double)fim-(double)inicio)/CLOCKS_PER_SEC);
		printf("\n\nTempo total para ordenar: %f (segundos.milesimos)\n\n\n",tempo);

	arquivo = fopen("Ordenados.txt","w");
	if(!arquivo)
	{
		printf("Arquivo nao pode ser criado");
	}
		for (indice = 0; indice < TAM; indice++)
		{
    			fprintf(arquivo,"%d\n",vetor[indice]);
		}
		fclose(arquivo);

free(vetor);
return 0;
}
//###############################################################

Essa é uma imagem da tela do notebook antes da execução do algoritmo.

Após alguns segundos de execução o consumo de memoria e processador tiveram um aumento significativo em relação ao estado inicial.

O tamanho dos arquivos de dados gerados pelo algoritmo ficou com tamanho de 847,5 MB. Veja a imagem abaixo.

O tempo total que o algoritmo levou para ordenar os 100.000.000 elementos foi de 45 segundos e 320000 milésimos de segundos (45.320000).

OBS: A cada nova execução do algoritmo os valores gerado serão diferentes e com a ordem diferente o que poderá influenciar no tempo de execução do mesmo!

Ate a próxima…