algoritmos_ordenacao.c

// TODO: Calcular corretamente as Permutações e Comparações dos Algoritmos
// TODO: Implementar Busca Sequêncial e Binária para 2ª parte do exercício

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

#define MAX_EXIBICAO_VETOR 10
#define MAX_RAND 4096
#define NUM_BUCKET 10
#define TAM_VETOR 1024
#define TAM_VETOR_BUCKET TAM_VETOR

typedef struct bucket {
    int topo;
    int v[TAM_VETOR_BUCKET];
} bucket;

int permutacoes, comparacoes; 

int separa(int v[], int p, int r);
void bubble(int v[], int tam);

void selection_sort(int * v, int tam);
void quick_sort(int* v, int p, int r);
void bucket_sort(int* v, int tam);

void popula_vetor(int* v, int tam, int rand_limit);
void exibe_vetor(int * v, int tam, char* descricao);
int* clone_vetor(int const* src, int len);

int main(int argc, char** argv)
{
    int v[TAM_VETOR];
    int total_permutacoes_selection = 0, total_permutacoes_quick = 0, total_permutacoes_bucket = 0,
        total_comparacoes_selection = 0, total_comparacoes_quick = 0, total_comparacoes_bucket = 0;

    popula_vetor(v, TAM_VETOR, MAX_RAND);

    for (int i = 0; i < 100; i++) {
        permutacoes = 0, comparacoes = 0;
	    int* v_selection = clone_vetor(v, TAM_VETOR);
	    selection_sort(v_selection, TAM_VETOR);

        total_comparacoes_selection += comparacoes;
        total_permutacoes_selection += permutacoes;

        permutacoes = 0, comparacoes = 0;
	    int* v_quick = clone_vetor(v, TAM_VETOR);
	    quick_sort(v_quick, 0, TAM_VETOR);

        total_comparacoes_quick += comparacoes;
        total_permutacoes_quick += permutacoes;

        permutacoes = 0, comparacoes = 0;
	    int* v_bucket = clone_vetor(v, TAM_VETOR);
	    bucket_sort(v_bucket, TAM_VETOR);

        total_comparacoes_bucket += comparacoes;
        total_permutacoes_bucket += permutacoes;
    }

    printf("Media de Comparações/Permutações nos algoritmos:\n\n");
 
    printf("%20s: %d/%d \n", "Selection Sort", total_comparacoes_selection / 100, total_permutacoes_selection / 100); 

    printf("%20s: %d/%d \n", "Quick Sort", total_comparacoes_quick / 100, total_permutacoes_quick / 100); 

    printf("%20s: %d/%d \n", "Bucket Sort", total_comparacoes_bucket / 100, total_permutacoes_bucket / 100); 
}

void selection_sort(int * v, int tam)
{
    int i, j, k, swap;

    for (i = 0; i < tam; i++) {

        k = i;

        for (j = i + 1; j < tam; j++) {
            if (v[k] > v[j]) {            
                k = j;
                comparacoes++; // FIXME
            }
        }

        if (k != i) {
            swap = v[i];
            v[i] = v[k];
            v[k] = swap;
 
            permutacoes++; // FIXME
        }
    }
}

int separa(int v[], int p, int r) 
{
    int c = v[p], i = p + 1, j = r, t;

    while (i <= j) {
 
        if (v[i] <= c) {
            v[i - 1] = v[i];
            ++i; 
		} else {
            t = v[i], v[i] = v[j], v[j] = t;
            --j; 
        }

        comparacoes++; // FIXME
        permutacoes++; // FIXME
    }

    v[j] = c;

    return j; 
}

void quick_sort(int* v, int p, int r)
{
    int j;

    while (p < r) {      

        j = separa(v, p, r);

        if (j - p < r - j) {     
            quick_sort(v, p, j-1);
            p = j + 1;            
        } else {                 
            quick_sort(v, j+1, r);
            r = j - 1;
        }
    }
}

void bucket_sort(int* v, int tam)
{
	int i,j,k;
    bucket b[NUM_BUCKET];

	for (i = 0; i < NUM_BUCKET; i++) 
		b[i].topo = 0;

	for (i = 0; i < tam; i++) {
		j = NUM_BUCKET - 1;
		while (1) {
			if (j < 0)
				break;

			if (v[i] > j * 10) {
				b[j].v[ b[j].topo ] = v[i];
				(b[j].topo)++;
				break;
			}

			j--;
		}
	}

	for (i = 0; i < NUM_BUCKET; i++) {
		if (!b[i].topo)
			continue;
			
		bubble(b[i].v, b[i].topo);
	}

	for (i = 0, j = 0; j < NUM_BUCKET; j++) {
		for (k = 0; k < b[j].topo; k++) {
			v[i] = b[j].v[k];
			i++;

            permutacoes++;
		}  
	}
}

void bubble(int v[], int tam)
{
	int i, j, swap, flag;

	for (j = 0; j < tam - 1; j++) {
		flag = 0;

		for (i = 0; i < tam - 1; i++) {
			if (v[i+1] < v[i]) {
				swap = v[i];
				v[i] = v[i+1];
				v[i+1] = swap;
				flag = 1;

                permutacoes++; // FIXME
			}
		}

		if (!flag)
			break;
	}
}

void popula_vetor(int* v, int tam, int rand_limit)
{
    srand((unsigned) time(NULL));

    for (int i = 0; i < tam; i++) {
        v[i] = rand() % rand_limit;
    }
}

void exibe_vetor(int * v, int tam, char* descricao)
{
	printf("%s [%d/%d]\n", descricao, comparacoes, permutacoes);

    for (int i = 0; i < tam; i++) {

        printf("[%04d]", v[i]);

        if (i > 0 && i % 10 == 0) {
            printf("\n");
        }
    }

    printf("\n");
}

int* clone_vetor(int const * src, int len)
{
    int* p = malloc(len * sizeof(int));
    memcpy(p, src, len * sizeof(int));
    return p;
}