BucketSort_13513051_13513061

Bucket.c

+#include <stdio.h>
+#include <mpi.h>
+#include <stdlib.h>
+
+void qusort(int arr[20], int l, int r){
+ int i,j,pivot,tmp;
+ if(l<r){
+   pivot=l;
+   i=l;
+   j=r;
+   while(i<j){
+     while(arr[i]<=arr[pivot] && i<r)
+        i++;
+     while(arr[j]>arr[pivot])
+        j--;
+     if(i<j)
+     {
+        tmp=arr[i];
+        arr[i]=arr[j];
+        arr[j]=tmp; 
+     }
+   }
+   tmp=arr[pivot];
+   arr[pivot]=arr[j];
+   arr[j]=tmp;
+
+   qusort(arr,l,j-1);
+   qusort(arr,j+1,r);
+ }
+}
+
+int main(int argc, char** argv){
+	int world_rank, world_size,nEl,nProc,i,rc;
+	double time = 0.0;
+	MPI_Status Stat;
+	if(argc!=3){
+		return 0;
+	}
+	nEl = atoi(argv[1]);
+	nProc = atoi(argv[2]);
+	int *arInt = (int *)malloc(sizeof(int)*nEl);
+	int **arIntn = (int **)malloc(sizeof(int*)*nProc+1);
+	for(i=0;i<nProc;i++){
+		arIntn[i]= (int *)malloc(sizeof(int)*nEl);
+	}
+	int *arCount = (int *) malloc (sizeof(int)*nProc+1);
+
+	MPI_Init(&argc,&argv);
+	MPI_Barrier(MPI_COMM_WORLD);
+        time -= MPI_Wtime();
+
+	MPI_Comm_rank(MPI_COMM_WORLD,&world_rank);
+	MPI_Comm_size(MPI_COMM_WORLD,&world_size);
+	if (world_rank==0){
+		for(i=0;i<nEl;i++){
+        		arInt[i]=rand()%(nEl);               
+		}
+		//for(i=0;i<nEl;i++) printf("%d\n",arInt[i]);
+		int j,xxx;
+		for(i=0;i<nProc;i++) arCount[i]=0;
+		
+		for(i=0;i<nEl;i++){
+			for(j=1;j<nProc;j++){
+				if (nEl%(nProc-1)!=0)	 xxx = nEl/(nProc-1) +1;
+				else xxx=nEl/(nProc-1);
+//				printf("Batas bawah:%d, Batas atas:%d\n", xxx*(j-1),xxx*j);
+				if (arInt[i] >= xxx*(j-1) && arInt[i] < xxx*j){
+					arIntn[j][arCount[j]]=arInt[i];	
+					arCount[j]++;
+//					printf("%d %d %d\n",j,arIntn[j][arCount[j]],arCount[j] );
+				}
+			}	
+		}
+		for(j=1;j<nProc;j++){
+		rc = MPI_Send(&arCount[j],1,MPI_INT,j,0,MPI_COMM_WORLD);
+        	rc = MPI_Send(arIntn[j],arCount[j],MPI_INT,j,1,MPI_COMM_WORLD);
+        }
+		for(j=1;j<nProc;j++){
+            rc = MPI_Recv(arIntn[j],arCount[j],MPI_INT,j,1,MPI_COMM_WORLD,&Stat);
+           /* printf("Receive message from %d\n",j );
+            for ( i = 0; i < arCount[j]; i++)
+            {
+            	printf("%d ", arIntn[j][i]);
+            }
+            printf("\n");*/
+    	}
+	}else{
+		int j,ndumm;
+		int *aI;
+		for(j=1;j<nProc;j++){
+        		if(world_rank==j){
+			 rc = MPI_Recv(&arCount[j],1,MPI_INT,0,0,MPI_COMM_WORLD,&Stat);
+			 rc = MPI_Recv(arIntn[j],arCount[j],MPI_INT,0,1,MPI_COMM_WORLD,&Stat);
+			}
+		}
+         
+		qusort(arIntn[world_rank],0,arCount[world_rank]-1);
+		rc = MPI_Send(arIntn[world_rank],arCount[world_rank],MPI_INT,0,1,MPI_COMM_WORLD);
+	}
+
+	MPI_Barrier(MPI_COMM_WORLD);
+        time += MPI_Wtime();
+        if(world_rank==0) printf("Running time: %lf s\n",time);
+	MPI_Finalize();
+	free(arIntn);
+	free(arInt);
+	free(arCount);
+
+	return 0;
+}