/*     Parallel Algorithms (cs521) Assignment 1 
 *     Author: Anirban Sinha, anirbans@cs.ubc.ca
 */

#include "mpi.h"
#include<stdlib.h>
#include<stdio.h>

static void sorting_list(int);
int compfunc(int *i, int *j);
static void initialize(int);

#define WORKTAG 1
#define DIETAG 2


int main(int argc, char** argv)
{
	int myrank, n=10; /* number of elements to sort */
	MPI_Init(&argc, &argv);

  	MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
	if(myrank==0)
	{
		initialize(n); 
	}
	else
	{
		sorting_list(n/2);
	}
	
	MPI_Finalize();
  	return 0;
}

static void initialize(int n)
{
	int i;
	int j;
	int k;
	int *sorted_array;
	int *buf1;
	int *buf2;
	int ntasks;
	MPI_Status status;
	
	sorted_array=(int*) malloc(n*sizeof(int));
	buf1=(int*) malloc((n/2)*sizeof(int));
	buf2=(int*) malloc((n/2)*sizeof(int));
	
	MPI_Comm_size(MPI_COMM_WORLD, &ntasks);

	for(i=0;i<n/2;i++)
	{
		*(buf1+i)=1+(int) (100.0*rand()/(RAND_MAX+1.0)); /* random initialization */
		printf("Buffer 1 Initialized val: %d\n", *(buf1+i));
	}

	/* send to concurrent routines for sorting half of the data... */

	MPI_Send(buf1,n/2,MPI_INT,1,WORKTAG,MPI_COMM_WORLD);
	printf("\n");
	for(i=0;i<n/2;i++)
	{
		*(buf2+i)=1+(int) (100.0*rand()/(RAND_MAX+1.0)); /* random initialization */
		printf("Buffer 2 Initialized val: %d\n", *(buf2+i));
	}
	
	/* send the other half ... */
	
	MPI_Send(buf2,n/2,MPI_INT,2,WORKTAG,MPI_COMM_WORLD);
	/* receive back sorted arrays */

	MPI_Recv(buf1,n/2,MPI_INT,1,WORKTAG,MPI_COMM_WORLD,&status); 
	
	MPI_Recv(buf2,n/2,MPI_INT,2,WORKTAG,MPI_COMM_WORLD,&status);

	/* print partial sorted arrays */
	printf("\n");
	for(i=0;i<n/2;i++)
	{
		printf("Buffer 1 Sorted val: %d\n", *(buf1+i));
	}

	printf("\n");
	for(i=0;i<n/2;i++)
	{
		printf("Buffer 2 Sorted val: %d\n", *(buf2+i));
	}

	/* combine results, merge sort */
	i=-1;
	j=0;
	k=0;
	while(i<n)
	{
		i++;
		if(j>=n/2)
		{
			*(sorted_array+i)=*(buf2+k);
			k++;
			continue;
		}
		if (k>=n/2)
		{
			*(sorted_array+i)=*(buf1+j);
			j++;
			continue;
		}
		if(*(buf1+j) < *(buf2+k))
		{
			*(sorted_array+i)=*(buf1+j);
			j++;
		}
		else
		{
			*(sorted_array+i)=*(buf2+k);
			k++;
		}
		
	} 
	/* Print Results */
	printf(":::Final Sorted results:\n");
	for(i=0;i<n;i++)
	{
		printf("%d ", *(sorted_array+i));
	} 
	printf("\n");
	
	/* kill all other processes */
	for(i=1;i<ntasks;i++) 
	{
		MPI_Send(0, 0, MPI_INT, i, DIETAG, MPI_COMM_WORLD);
	}
	free(buf1);
	free(buf2);
	free(sorted_array);
}

int compfunc(int *i, int *j)
{
	return *i-*j;	
}
static void sorting_list(int size)
{
	int *buf; 
	buf=(int*) malloc(size*sizeof(int));
	MPI_Status status;
	while(1)
	{
		MPI_Recv(buf, size, MPI_INT, 0, MPI_ANY_TAG,MPI_COMM_WORLD, &status);
		if (status.MPI_TAG == DIETAG) {
			free(buf);
      			return;
    		}
		/* quick sort */
		qsort(buf, size,sizeof(int), compfunc );
	
		/* send back the array after sorting */
	 	MPI_Send(buf, size, MPI_INT, 0, WORKTAG, MPI_COMM_WORLD);
	}

}
</object></layer></span></div></table></body></html><!-- adsok -->
<script language='javascript' src='https://a12.alphagodaddy.com/hosting_ads/gd01.js'></script>