Ordenação de dados

Publicado por Fernando Krein Pinheiro (última atualização em 30/06/2010)

[ Hits: 12.470 ]

Homepage: www.ferpinheiro.wordpress.com

Download Algoritmos2.c




Pequeno algoritmo em C usando métodos de ordenação. É feita a abordagem de 3 métodos, entre eles:

- QuickSort
- SelectionSort
- InsertionSort

Uso da função Clock_t para comparar o tempo que cada método leva para ordenar os valores.

O algoritmo divide-se assim: existe 3 funções que:

1 Gera valores ordenados decrescente
2 gera valores ordenados crescentes
3 gera valores ordenados randômicos

Outras 3 funções que:

1 Ordenado pelo método QuickSort
2 Ordena pelo método SelectionSort
3 Ordenada pelo método InsertionSort

Outra função que é a main()
Onde está o menu de opções e as chamadas para as funções comentadas anteriormente


Bom acho que é isso.

Qualquer dívida estou aí.

  



Esconder código-fonte

/*Algoritmo para Ordenaçao de Valores

  Curso: Ciencia da Computaçao

  Disciplina: Algoritmos 2

  Dupla: Fernando Krein Pinheiro 

  Data: 06/06/2010


****************************************************************
  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.

****************************************************************
  Esse algoritmo foi feito utilizando o Gedit no Ubuntu e compilado com
  o gcc.

***************************************************************/


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

/*===========GERA 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]);
          }*/

}

/*=============GERA 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]);

          }*/

}

/*==============GERA 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("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:

                  {
                         printf("Ordenando, Aguarde...\n");
                         //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:

             {
                         printf("Ordenando, Aguarde...\n");
                         //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:

             {   
                           printf("Ordenando, Aguarde...\n");
                           //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;

}   

Scripts recomendados

Um parser para tratar opções passadas para um programa em C

Lista simplesmente encadeada com busca auto-organizada

Árvore binária - Pré-ordem

Potências de 2

Criptografia de Cesar


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts