/*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;

}