Análise dos Métodos de Ordenação usados em Algoritmos Computacionais

Este artigo apresenta uma análise de alguns dos métodos de ordenação usados em algoritmos computacionais. Comparando as iterações feitas e o tempo em que cada algoritmo leva para ordenar certa quantidade de dados em um vetor podendo ser este de ordem crescente, decrescente ou randômico.

[ Hits: 31.771 ]

Por: Fernando Krein Pinheiro em 29/04/2011


Algoritmo completo



Algoritmo usado para fazer os testes.

/*Algoritmo para Ordenação de Valores

  Nome: Fernando Krein Pinheiro

  Data: 28/06/2010

*/

/******

  Obs.: Para Ordenar com vetores de ordem Crescente ou decrescente

  precisa comentar as chamadas de funçoes na main() deixando apenas

  uma função de ordenação. Para vetores de diferentes tamanho mude

  a Constante TAM nos arquivos cabeçalhos logo abaixo.

  *****

  Esse Programa foi escrito usando Gedit (S.O Ubuntu, 32 Bits)
  e compilado usando gcc.

*/


#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;

     }

          /*for(i=0;i<num;i++)

          {

              printf("%d\n",vet[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;

     }

         /* for(i=0;i<num;i++)

          {

              printf("%d\n",vet[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;  

        }

        /*for(i=0;i<TAM;i++)

        {

             printf("%d\n",vet[i]);

        }*/

}

/* 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){/*serve apenas para mostrar o valor ordenado afim de conferencia*/

     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("cls");                

    

    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)(((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)(((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)(((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;

}

Página anterior     Próxima página

Páginas do artigo
   1. Introdução
   2. Desenvolvimento
   3. Testes baseados em tempo
   4. Comparações entre os métodos
   5. Algoritmo completo
   6. Conclusões
Outros artigos deste autor
Nenhum artigo encontrado.
Leitura recomendada

Linguagem C - Árvores Binárias

Linguagem C - Listas Duplamente Encadeadas

Otimização de algoritmos

Tutorial SDL

Algoritmo... como fazer?

  
Comentários
[1] Comentário enviado por ricardoolonca em 02/05/2011 - 10:04h

Não sou desenvolvedor, mas quero parabenizá-lo pelo ótimo artigo. A forma de escrever e apresentar os fatos com comparações em diferentes ambientes foi muito legal.

Parabéns.

[2] Comentário enviado por fernandopinheiro em 02/05/2011 - 20:00h

Obrigado pelas palavras amigo maionesebr, é esse tipo de comentário que me deixa motivado ha compartilhar o pouco que sei.

[3] Comentário enviado por pablo.ribeiro em 25/09/2011 - 17:27h

muito bom, esta me ajudando para estudar para faculdade rs


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts