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