Analises de algoritmos de ordenações

[arsenium123 0]

Bem, tenho um trabalho para fazer e devo analisar os respectivos algoritmos

 

-> Contagem (Counting Sort)

-> Bubble

-> Insertion

-> Selection

 

quanto ao tempo de execução e o numero de trocas, para um vetor de 100 mil posições.

 

Só queria saber se o que eu fiz está certo (ou perto de estar), se é mais ou menos aquele numero de trocas, tempo execução (a execução pode variar, claro), mas principalmente quanto ao numero de trocas... Acho que a do bubble deveria ser mais, e a do algoritmo de contagem eu não tenho ideia de como contar as trocas. Na verdade pensei em comparar o vetor final com o inicial, e se o elemento na posição i for diferente do vetor inicial é porque ele trocou de posição, mas não deve ser isso.

 

Bem, desculpem se aparecer alguma coisa muito absurda na implementação, ou mesmo a desorganização, ou algumas gambiarras haha

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

#define tam 100000
#define N 10

int i, j;
float inicio, fim;

int crescente (int *vetor) 		//função para ordenar os vetor antes de jogar nas funções de ordenação (funcionando)
{

	int *aux, *resposta;

	resposta = (int*) calloc (tam, sizeof(int));
	aux = (int*) calloc (tam + 1, sizeof(int));

	for (i = 0; i < tam + 1; i++)
		aux[i] = 0;

	for (i = 0; i < tam; i++)
		aux[vetor[i]]++;

	for (i = 1; i < tam + 1; i++)
		aux[i] += aux[i - 1];

	for (i = 0; i < tam; i++)
	{
		resposta[aux[vetor[i]] - 1] = vetor[i];
		aux[vetor[i]]--;
	}

	for (i = 0; i < tam; i++)
		vetor[i] = resposta[i];

	return *vetor;
}

int decrescente (int *vetor) 		//funcionando
{

	int aux;

	for (i = 0; i < tam; i++)
	{
		for (j = i + 1; j < tam; j++)
		{
			if (vetor[i] < vetor[j])
			{
				aux = vetor[i];
				vetor[i] = vetor[j];
				vetor [j] = aux;
			}
		}
	}

	return *vetor;
}

int crescente_sel (int *vetor) 		//teve que ser criada pois a ordenação contagem estava dando erro no Selection
{

	int aux;

	for (i = 0; i < tam; i++)
	{
		for (j = i + 1; j < tam; j++)
		{
			if (vetor[i] > vetor[j])
			{
				aux = vetor[i];
				vetor[i] = vetor[j];
				vetor [j] = aux;
			}
		}
	}

	return *vetor;
}

long int bubble (int *vetor, float *tempo)
{

	long int trocas = 0;
	int aux;

	inicio = GetTickCount();
	for (i = 0; i < tam; i++)
	{
		for (j = i + 1; j < tam; j++)
		{
			if (vetor[i] > vetor[j])
			{
				aux = vetor[i];
				vetor[i] = vetor[j];
				vetor [j] = aux;
				trocas++;
			}
		}
	}
	fim = GetTickCount();

	*tempo = fim - inicio;

	return trocas;
}

unsigned long long int insertion (int *vetor, float *tempo)
{

	unsigned long long int trocas = 0, aux;

	inicio = GetTickCount();
	for (i = 1; i < tam; i++)
	{
		aux = vetor[i];
		j = i - 1;
		while (j >= 0 && vetor[j] > aux)
		{
			vetor[j + 1] = vetor[j];
			vetor[j] = aux;
			j--;
			trocas++;
		}
	}
	fim = GetTickCount();

	*tempo = fim - inicio;

	return trocas;
}

long int selection (int *vetor, float *tempo)
{

	long int trocas = 0, aux, menor;

	inicio = GetTickCount();
	for (i = 0; i < tam; i++)
	{
		menor = i;
		for (j = i + 1; j < tam; j++)
		{
			if (vetor[menor] > vetor[j])
			{
				menor = j;
			}
		}

		if (menor != i)
		{
			aux = vetor[i];
			vetor[i] = vetor[j];
			vetor[j] = aux;
			trocas++;
		}
	}
	fim = GetTickCount();

	*tempo = fim - inicio;

	return trocas;
}

void counting_sort (int *vetor, float *tempo)
{

	int *aux, *final;

	aux = (int*) calloc (tam + 1, sizeof(int));

	inicio = GetTickCount();
	for (i = 0; i < tam + 1; i++)
		aux[i] = 0;

	for (i = 0; i < tam; i++)
		aux[vetor[i]]++;

	for (i = 1; i < tam + 1; i++)
		aux[i] += aux[i - 1];

	final = (int*) calloc (tam, sizeof(int));

	for (i = 0; i < tam; i++)
	{
		final[aux[vetor[i]] - 1] = vetor[i];
		aux[vetor[i]]--;
	}

	for (i = 0; i < tam; i++)
		vetor[i] = final[i];

	fim = GetTickCount();

	*tempo = fim - inicio;

}
int main ()
{

	int *bub, *ins, *sel, *counting;
	float tempo = 0;
	long int trocas_selection, trocas_counting, trocas_bubble;
	unsigned long long int trocas_insertion;

	srand(time(NULL));

	bub = (int *) calloc (tam, sizeof(int));
	ins = (int*) calloc (tam, sizeof(int));
	sel = (int*) calloc (tam, sizeof(int));
	counting = (int*) calloc (tam, sizeof(int));

	for (i = 0; i < tam; i++)
	{
		bub[i] = rand() % 100;
		ins[i] = bub[i];
		sel[i] = ins[i];
		counting[i] = sel[i];
	}

	printf ("SORT -> TEMPO DE EXECUCAO EM SEGUNDOS - NUMERO DE TROCAS\n\n");
	printf ("Vetores Aleatorios:\n");
	printf ("Bubble ->  ");
	trocas_bubble = bubble(bub, &tempo);
	printf ("%.2f s - %ld trocas\n", tempo / 1000, trocas_bubble);
	printf ("Insertion ->  ");
	trocas_insertion = insertion(ins, &tempo);
	printf ("%.2f s - %llu trocas\n", tempo / 1000, trocas_insertion);
	printf ("Selection ->  ");
	trocas_selection = selection(sel, &tempo);
	printf ("%.2f s - %ld trocas\n", tempo / 1000, trocas_selection);
	printf ("Counting ->  ");
	counting_sort(counting, &tempo);
	printf ("%.2f s\n", tempo / 1000);

	printf ("\nVetores Crescentes:\n");
	printf ("Bubble ->  ");
	crescente(bub);
	trocas_bubble = bubble(bub, &tempo);
	printf ("%.2f s - %ld trocas\n", tempo / 1000, trocas_bubble);
	printf ("Insertion ->  ");
	crescente(ins);
	trocas_insertion = insertion(ins, &tempo);
	printf ("%.2f s - %llu trocas\n", tempo / 1000, trocas_insertion);
	printf ("Selection ->  ");
	crescente_sel(sel);
	trocas_selection = selection(sel, &tempo);
	printf ("%.2f s - %ld trocas\n", tempo / 1000, trocas_selection);
	printf ("Counting ->  ");
	crescente(counting);
	counting_sort(counting, &tempo);
	printf ("%.2f s\n", tempo / 1000);

	printf ("\nVetores Derescentes:\n");
	printf ("Bubble ->  ");
	decrescente(bub);
	trocas_bubble = bubble(bub, &tempo);
	printf ("%.2f s - %ld trocas\n", tempo / 1000, trocas_bubble);
	printf ("Insertion ->  ");
	decrescente(ins);
	trocas_insertion = insertion(ins, &tempo);
	printf ("%.2f s - %llu trocas\n", tempo / 1000, trocas_insertion);
	printf ("Selection ->  ");
	decrescente(sel);
	trocas_selection = selection(sel, &tempo);
	printf ("%.2f s - %ld trocas\n", tempo / 1000, trocas_selection);
	printf ("Counting ->  ");
	decrescente(counting);
	counting_sort(counting, &tempo);
	printf ("%.2f s\n", tempo / 1000);

	return 0;
}

[_Isis_ 202]

Vc tem que analisar ou implementar? São duas coisas diferentes.

Por análise de algoritmos, pelo que você comentou, vai usar notação assintótica p/ "descrever"/comparar o desempenho entre eles (http://www.ime.usp.br/~pf/analise_de_algoritmos/)