Descrição
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í.
[ Download:
Algoritmos2.c ]
[
Enviar nova versão ]
[ 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
Aritmética de ponteiros
Duplamente Circular
Deep First Search
Função Hash básica
Fila
Comentários
| Nenhum comentário foi encontrado. |
Indicar para um amigo
Escrever um script