Ordenação de Elementos em C.

Desenvolvi esse algoritmo para demonstrar a diferença entre três métodos de ordenação usados na computação. Faço uso de uma função time() para coletar o tempo gasto por cada método para uma posterior comparação entre eles.

O algoritmo é simples mas mesmo assim é preciso fazer uma introdução antes: Os três métodos usados foram QuickSort, SelectioSort e InsertionSort, existe três tipo de ordenação que poderão ser feitas utilizando um vetor de elementos randomizado, ordenado crescente e ordenado decrescente, também é possível escolher o tamanho do vetor que se quer ordenar, para isso basta modificar o valor da constante TAM definida por: #define TAM 100000

O algoritmo foi testado e programado para no máximo 200000 valores, um numero acima desse poderá gerar erros ou inconsistências na saídas do programa. O programa foi escrito no Gedit e compilado com o gcc no Linux(Ubuntu).

A função para verificar o tempo no Linux é essa: (double)(((double)fim-(double)inicio)/CLOCKS_PER_SEC);
Caso queira compilar no (ru)Windows você precisa trocar a função do Linux por essa: ((double)(fim-inicio))/CLK_TCK;
Lembro que o tempo de execução de cada método poderá não ser o mesmo se executado em diferentes configurações de hardware (memoria, processador).

/*********************************
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.
*********************************/
/***************************************************************
OBS: Para Ordenar com vetores de ordem Crescente ou decrescente
precisa comentar as chamdas de fuçoes na main() deixando apenas
uma funçao de ordenação. Para vetores de diferentes tamanho mude
a Constante TAM nos arquivos cabeçalhos logo abaixo.
***************************************************************/

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

/*=======================VETOR ORDENADO DECRESCENTE===============================*/
void vet_ordenado_decrescente(int vet[],int num)
{
     int i;
     printf("Vetor em Ordem Decrescente\n");
     for(i=num;i>0;i--)
     {
           vet[i]=num-i;
     }
}

/*=======================VETOR_ORDENADO CRESCENTE==================================*/

void vet_ordenado(int vet[],int num)
{
     int i;
     printf("Vetor em Ordem Crescente\n");
     for(i=0;i<num;i++)
     {
           vet[i]=1+i;
     }
}

/*=======================VETOR_RANDOMIZADO========================================*/
void randomiza(int vet[],int num)
{
     int i;
     srand(time(NULL));
        printf("Vetor em Ordem Randomica\n");
        for (i=0; i<TAM; i++)
        {
                vet[i]=rand() % TAM;
        }
}

/*=====================QUICK_SORT==================================================*/
void ordena_quick(int vet[], int esquerda, int direita)
{
    int i, j;
    int x, y;
    i=esquerda; j=direita;
    x=vet[(esquerda+direita)/2];/*gera a media dos valores para escolher o pivo*/

  do
  {
    while(vet[i]<x && i<direita)
    i++;
         while(x<vet[j] && j>esquerda)
	 j--;
     if(i<=j)
     {
         y=vet[i];
         vet[i]=vet[j];
         vet[j]=y;
         i++;
         j--;
     }

   }while(i<=j);

    if(esquerda<j)
    ordena_quick(vet, esquerda, j);
           if(i<direita)
           ordena_quick(vet, i, direita);
}
void imprime_quick(int vet[],int num)
{
     int i=0;
     printf("\nORDENADO PELO METODO QUICKSORT:\n");
     while (i<num)
    {
           printf("%d\n", vet[i]);
           i++;
    }
}

/*=======================SELECTION_SORT============================================*/
void ordena_selection(int vet[], int num)
{
     int menor, i=0, y, aux;
     while (i<num)
	{
           	menor=vet[i];
           	y=i+1;
           	while (y<num)
		{
                 	if (vet[y] < menor)
			{
                                  aux = vet[y];
                                  vet[y] = menor;
                                  menor = aux;
                        }
                     y++;
                 }
           vet[i]=menor;
           i++;
       }
}
int  imprime_selection(int vet[],int num)
{
     int i=0;
     printf("\nORDENADO PELO METODO SELECTION:\n");
     while (i<num)
     {
           	printf("%d\n",vet[i]);
           	i++;
        }
}

/*=======================INSERTION_SORT============================================*/
void ordena_insertion(int vet[], int num)
{
        int i, j;
        int key;
        for (j=1;j<num;++j)
	{
                key = vet[j];
                i = j - 1;
                while (vet[i] > key && i >= 0)
		 {
                        vet[i+1] = vet[i];
                        --i;
                 }
              vet[i+1] = key;
        }
}
int  imprime_insertion(int vet[],int num)
{
     int i=0;
     printf("\nORDENADO PELO METODO INSERTION:\n");
     while (i<num)
	{
           	printf("%d\n", vet[i]);
           	i++;
        }
}

/*======================INICIO_DA_MAIN================================================*/
int main()
{
        clock_t inicio,fim;
    	int vet[TAM],i,num=0,opcao,op;
        double time_quick=0,time_selection=0,time_insertion=0;
    	system("clear");
    do
    {
      printf("\n===========MENU==========\n\n");
      printf("1 - QuickSort\n2 - SelectionSort\n3 - InsertionSort\n4 - Mostrar Tempos\n5 - Sair\n");
      printf("===========================[ ]\b\b");
      scanf("%d",&opcao);
      if(opcao<1||opcao>4)
      {
          exit(1);
      }
  switch(opcao)
  {
       case 1:
       {
           //vet_ordenado_decrescente(vet,TAM);
           //vet_ordenado(vet,TAM);
             randomiza(vet,TAM);

	        inicio=clock();
                ordena_quick(vet, 0, TAM-1);
                fim=clock();
                time_quick = /*((double)(fim-inicio))/CLK_TCK;*/(double)(((double)fim-(double)inicio)/CLOCKS_PER_SEC);
                printf("\n%3.3f Segundos para Ordenar %d numeros com o Metodo QuickSort\n\n",time_quick,TAM);
                //imprime_quick(vet,TAM);
                break;

         }
         case 2:
	 {
             //vet_ordenado_decrescente(vet,TAM);
             //vet_ordenado(vet,TAM);
               randomiza(vet,TAM);

                 inicio=clock();
                 ordena_selection(vet,TAM);
                 fim=clock();
                 time_selection = /*((double)(fim-inicio))/CLK_TCK;*/(double)(((double)fim-(double)inicio)/CLOCKS_PER_SEC);                	               printf("\n%3.4f Segundos para Ordenar %d numeros com o Metodo SelectionSort\n\n",time_selection,TAM);
		 //imprime_selection(vet,TAM);
                 break;

	  }
          case 3:
	  {
              //vet_ordenado_decrescente(vet,TAM);
              //vet_ordenado(vet,TAM);
                randomiza(vet,TAM);

	          inicio=clock();
    		  ordena_insertion(vet,TAM);
		  fim=clock();
		  time_insertion = /*((double)(fim-inicio))/CLK_TCK; */(double)(((double)fim-(double)inicio)/CLOCKS_PER_SEC);                      		               printf("\n%3.4f Segundos para Ordenar %d numeros com o Metodo InsertionSort\n\n",time_insertion,TAM);
                  //imprime_insertion(vet,TAM);
                  break;

          }
          case 4:
          {
                      printf("Tempo do QuickSort = %3.3f s\n",time_quick);
                      printf("Tempo do SelectionSort = %3.3f s\n",time_selection);
                      printf("Tempo do InsertionSort = %3.3f s\n",time_insertion);
                      break;
          }

     }

    }while(opcao>0||opcao<5);
return 0;
}

Confira uma versão desse post AQUI

Anúncios
por ferpinheiro Postado em C/C++

7 comentários em “Ordenação de Elementos em C.

  1. Cara, da erro quando defino máx acima de 100mil, eu to querendo ver o tempo do quick em vetores c/ 1Milhão, tu sabe como resolver isso?!

    • Voce precisa alocar memoria dinamicamente, pois com o uso do vetor dessa maneira ele estoura o limite de memoria, por isso da o erro.

      Use a função malloc() para alocar o vetor do tamanho que voce quiser nesse caso “TAM” e então poderá usar para quantia de valores que quiser.

  2. usei vetor = (int*) malloc(sizeof(int)*MAX);
    para criar o vetor, e funcionou *_*, consegui ordenar 10milhoes, sem erros! hehe

  3. Pingback: Ordenando elementos com qsort() – C/C++ « Compartilhar é preciso.

  4. olá, td bem?
    Como faço pra ler um arquivo csv, fazer a ordenação pelos metodos implementados e imprimir o resultado da ordenação? No aguardo! Urgenteee!

    Por favor, me socorraaa!

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s