💻 Código das comparações de performance entre os algoritmos de ordenação do exercício de Estrutura de Dados do curso de Engenharia de Software.
License: MIT License
C 100.00%
comparacao-ordenacao-c-ansi's Introduction
Comparação de Performance de Métodos de Ordenação
Equipe
Cristian Prochnow
Gustavo Henrique Dias
Lucas Willian de Souza Serpa
Marlon de Souza
Ryan Gabriel Mazzei Bromati
Algoritmos
Insertion Sort
voidinsertionSort(int*vet) {
inti, j, atual, qtd_trocas=0, qtd_comparacoes=0;
// Ponto do algoritmo para iniciar o tempo de execuçãofloattempo_inicial=clock();
for (i=1; i<TAMANHO; i++) {
atual=vet[i];
j=i-1;
while (j >= 0&&vet[j] >atual) {
// Ponto do algoritmo para contar as comparaçõesqtd_comparacoes++;
vet[j+1] =vet[j];
j=j-1;
// Ponto do algoritmo para contar as trocasqtd_trocas++;
}
vet[j+1] =atual;
}
// Ponto do algoritmo para calcular o tempo de execuçãofloattempo_final=clock() -tempo_inicial;
// Saída de dadosprintf("Quantidade de comparacoes: %i\n", qtd_comparacoes);
printf("Quantidade de trocas: %i\n", qtd_trocas);
printf("Tempo de execucao do algoritmo: %.3f\n", tempo_final / CLOCKS_PER_SEC);
}
Selection Sort
voidselectionSort(int*vet)
{
intn, troca, i, aux, qtd_trocas, qtd_comparacoes;
n=1;
troca=1;
qtd_trocas=0;
qtd_comparacoes=0;
// Ponto do algoritmo para iniciar o tempo de execuçãofloattempo_inicial=clock();
intvMenor;
intvAux;
intvTemp;
intvTroca;
intpVetor[TAMANHO];
for(vAux=0; vAux<TAMANHO-1; vAux++)
{
vMenor=vAux;
for (vTemp=vAux+1; vTemp<TAMANHO; vTemp++)
{
qtd_comparacoes++;
if (vet[vTemp] <vet[vMenor])
{
vMenor=vTemp;
}
}
if (vMenor!=vAux)
{
vTroca=vet[vAux];
vet[vAux] =pVetor[vMenor];
vet[vMenor] =vTroca;
qtd_trocas++;
}
}
// Ponto do algoritmo para calcular o tempo de execuçãofloattempo_final=clock() -tempo_inicial;
// Saída de dadosprintf("\nQuantidade de comparacoes: %i\n", qtd_comparacoes);
printf("Quantidade de trocas: %i\n", qtd_trocas);
printf("Tempo de execucao do algoritmo: %.3f", tempo_final / 1000);
}
floattempo_inicial=clock();
intqtd_trocas=0;
intqtd_comparacoes=0;
int*qtd_trocas_aux=&qtd_trocas;
int*qtd_comparacoes_aux=&qtd_comparacoes;
geraNumero(vet1, 3);
quickSort(vet1, 0, TAMANHO-1, qtd_trocas_aux, qtd_comparacoes_aux);
floattempo_final=clock() -tempo_inicial;
printf("\nQuantidade de comparacoes: %i\n", qtd_comparacoes);
printf("Quantidade de trocas: %i\n", qtd_trocas);
printf("Tempo de execucao do algoritmo: %.3f", tempo_final / 1000);
voidquickSort(int*vet, intini, intfim, int*qtd_trocas, int*qtd_comparacoes) {
intmeio, pivo, topo, i;
if (ini<fim) {
pivo=vet[ini];
topo=ini;
for (i=ini+1; i <= fim; i++) {
*qtd_comparacoes+=1;
if (vet[i] <pivo) {
vet[topo] =vet[i];
vet[i] =vet[topo+1];
topo++;
*qtd_trocas+=1;
}
}
vet[topo] =pivo;
meio=topo;
quickSort(vet, ini, meio, qtd_trocas, qtd_comparacoes);
quickSort(vet, meio+1, fim, qtd_trocas, qtd_comparacoes);
}
}
Bubble Sort
voidbubbleSort(int*vet)
{
intn, troca, i, aux, qtd_trocas, qtd_comparacoes;
n=1;
troca=1;
qtd_trocas=0;
qtd_comparacoes=0;
// Ponto do algoritmo para iniciar o tempo de execuçãofloattempo_inicial=clock();
while (n <= TAMANHO&&troca==1)
{
troca=0;
for (i=0; i <= TAMANHO-2; i++)
{
// Ponto do algoritmo para contar as comparaçõesqtd_comparacoes++;
if (vet[i] >vet[i+1])
{
// Ponto do algoritmo para contar as trocasqtd_trocas++;
troca=1;
aux=vet[i];
vet[i] =vet[i+1];
vet[i+1] =aux;
}
}
n=n+1;
}
// Ponto do algoritmo para calcular o tempo de execuçãofloattempo_final=clock() -tempo_inicial;
// Saída de dadosprintf("\nQuantidade de comparacoes: %i\n", qtd_comparacoes);
printf("Quantidade de trocas: %i\n", qtd_trocas);
printf("Tempo de execucao do algoritmo: %.3f", tempo_final / 1000);
}