C Programação paralela e distribuída

cristiano moreira · 20 de outubro de 2020

#include<stdio.h>
#include<stdlib.h>
//#include <pthread.h>
#include <sys/time.h>
#include<omp.h>
#define TAMANHO_VETOR 10000

void quickSort(int *vetor, int inicio, int fim);
void populaVetorDecrescente(int *endVetor, int tamanhoVetor);
int estaOrdenado(int *vetor, int tamanhoVetor);

int numChamadasRecursivas = 0;

int main(void){

    struct timeval start, end;
    double diff;
    srand(time(NULL)); //seed random

    int *vetor = (int *) malloc(TAMANHO_VETOR*sizeof(int));
    populaVetorDecrescente(vetor, TAMANHO_VETOR);

    #pragma omp parallel for
    for(int i = 0; i < TAMANHO_VETOR; i++){
        printf("%d ", vetor[i]);
    }
    puts("");

    gettimeofday(&start, NULL);
    quickSort(vetor, 0, TAMANHO_VETOR - 1);
    gettimeofday(&end, NULL);

    if(!estaOrdenado(vetor, TAMANHO_VETOR)){
		printf("Oops, vetor não foi ordenado pelo quickSort.\n");
	}

    //Calcula tempo...
    diff = ((end.tv_sec * 1000000 + end.tv_usec)
          - (start.tv_sec * 1000000 + start.tv_usec))/1000000.0;
    printf("Quicksort sequencial demorou %lfs para ordenar %d"
    " elementos...\n", diff, TAMANHO_VETOR);

/*
    for(int i = 0; i < TAMANHO_VETOR; i++){
        printf("%d ", vetor[i]);
    }
    puts("");
*/

    printf("Numero de chamadas recursivas: %d\n", numChamadasRecursivas);

    free(vetor);

}

void quickSort(int *vetor, int inicio, int fim){
    numChamadasRecursivas++;

    int i, j, meio, aux;
    i = inicio;
    j = fim;
    meio = vetor[(inicio + fim) / 2];
    //Repetir os passos abaixo enquanto i e j não se encontrarem, ou seja,
    //incremente i e decrementa j, sempre os testando contra o valor apontado
    //pelo pivô (meio) (avaça i se for < meio, e recua j se for > meio). Feito
    //isso, teremos dois sub-vetores (os < q meio e os > que meio)
    do{
        //1. Avança i enquanto valor apontado por ele for < meio.
        while(vetor[i] < meio){
            i++;
        }
        //2. Recua j enquanto valor apontado por ele for > meio.
        while(vetor[j] > meio){
            j--;
        }
        //3. Trocar os valor apontados por i e j.
        if(i <= j){
            aux = vetor[i];
            vetor[i] = vetor[j];
            vetor[j] = aux;
            i++;
            j--;
        }
    //Repete enquanto i e j não se encontrarem...
    }while(i <= j);

    //A partir daqui sub-divide-se a lista, pois todos os > que o meio estão
    //à direita e os menores à esquerda.
    //Repete, recursivamente, para os sub-vetores criados enquanto existirem +
    //de um elemento em cada lado.
    if(inicio < j){
        quickSort(vetor, inicio, j);
	}

    if(i < fim){
		quickSort(vetor, i, fim);
	}

}

//Função para popular um vetor de forma decrescente. Pior caso...
void populaVetorDecrescente(int *endVetor, int tamanhoVetor){
    int valor = tamanhoVetor, i;
    for(i = 0; i < tamanhoVetor; i++){
        endVetor[i] = valor--;
    }
}


//Verifica se vetor está ordenado (crescente...).
int estaOrdenado(int *vetor, int tamanhoVetor){
	for (int i = 1; i < tamanhoVetor; i ++){
		if (vetor[i] < vetor[i-1]){
			printf("posicao %d, %d < %d \n", i, vetor[i], vetor[i-1]);
			return 0;
		}
	}
	return 1;
}