gnome_sort_parallel.c

# include <stdio.h>
# include <stdlib.h>
# include <ctype.h>
# include <string.h>
# include <stdbool.h>
# include <mpi.h>
 
 /* declaração das funcoes
 */
void random_numbers(int *v, int tamanho);
void gnome_sort(int *a, int n);
void print(int vetor[], int size);
int* join(int *vetor, int size);

int main (int argc, char **argv){
	int size, i, j;

	int tamanho, tamanho_total;
	int rank, type = 99;
	
	// inicializa o MPI
	MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &size);
	MPI_Status status;

  	tamanho = atoi(argv[1]); // quantidade de processadores
	tamanho_total = tamanho * size;
	
	/* vetor com parte dos elementos que vai ser dividido entre os 
	processadores */
	int *vPart = (int*) calloc(tamanho, sizeof(int));
	int *vTotal = (int*) calloc(tamanho_total, sizeof(int)); // vetor com todos os elementos
	
	// * gera numeros aleatorios para o vetor
	random_numbers(vTotal, tamanho_total);
	
	
	if (rank == 0){
		printf("vetor desordenado \n");
	  print(vTotal, tamanho_total);
	}
	
	// divide o vetor entre os processadores
	// em cada processador, a variavel vPart vai conter alguns dos indices do vetor
	MPI_Scatter(vTotal, tamanho, MPI_INT, vPart, tamanho, MPI_INT, 0, MPI_COMM_WORLD);
	
	// ordena o vetor parcial (vPart)
	gnome_sort(vPart, tamanho);
	
	// junta todos os vetores parciais(vPart), jah que estes agora estao ordenados
	// no vetor total
	MPI_Gather(vPart, tamanho, MPI_INT, vTotal, tamanho, MPI_INT, 0, MPI_COMM_WORLD);
	
	// espera todos os processadores terminarem de ordernar o vetor
	MPI_Barrier(MPI_COMM_WORLD);
	  if (rank == 0){
	  	
	  	// coloca os numeros nas suas posicoes corretas
	  	vTotal = join(vTotal, tamanho_total);
	  	printf("vetor ordenado \n");
	  	print(vTotal, tamanho_total);
	  }
	  MPI_Finalize(); // termina o MPI
	  return 0;
}
 
/* funcao de ordenacao */
void gnome_sort(int *a, int n){
  int i=1, j=2, t;
# define swap(i, j) { t = a[i]; a[i] = a[j]; a[j] = t; } 
  while(i < n) {
    if (a[i - 1] > a[i]) {
      swap(i - 1, i);
      if (--i) continue;
    }
    i = j++;
  }
# undef swap
}
 // funcao que gera numeros aleatorios
void random_numbers(int *v, int tamanho){
	int i;
	srand(time(0));
	for(i = 0; i < tamanho; i++){
		v[i] = rand() % 100;	
	}
}

// funcao pra imprimir os dados do vetor
void print(int vetor[], int size){
	int i;
  for(i = 0; i < size;i++){
		printf("%d - ", vetor[i]);
	}
	printf("\n");
}

int* join(int *vetor, int size){
 int i, j, eleito;
 for (i = 1; i < size; i++){
    eleito = vetor[i];
    j = i - 1;
    while ((j>=0) && (eleito < vetor[j])) {
       vetor[j+1] = vetor[j];
       j--;
    }
    vetor[j+1] = eleito;
 }
 return vetor;
}

gnome_sort_sequencial.c

# include <stdio.h>
# include <stdlib.h>
# include <ctype.h>
# include <string.h>
 
void random_numbers(int *v, int tamanho);
void gnome_sort(int *a, int n);
void print(int vetor[], int size);

int main (int argc, char **argv){
	int  i, j;

	int tamanho;
        tamanho = atoi(argv[1]);
	int *vTotal = (int*) calloc(tamanho, sizeof(int));

	random_numbers(vTotal, tamanho);
	printf("vetor desordenado \n");
	print(vTotal, tamanho);

	gnome_sort(vTotal, tamanho);
	printf("vetor ordenado \n");
	print(vTotal, tamanho);
	 return 0;
}
 
void gnome_sort(int *a, int n){
  int i=1, j=2, t;
# define swap(i, j) { t = a[i]; a[i] = a[j]; a[j] = t; } 
  while(i < n) {
    if (a[i - 1] > a[i]) {
      swap(i - 1, i);
      if (--i) continue;
    }
    i = j++;
  }
# undef swap
}
 
void random_numbers(int *v, int tamanho){
	int i;
	srand(time(0));
	for(i = 0; i < tamanho; i++){
		v[i] = rand() % 100;	
	}
}

void print(int vetor[], int size){
	int i;
  for(i = 0; i < size;i++){
		printf("%d - ", vetor[i]);
	}
	printf("\n");
}