#include <stdio.h>#include <stdlib.h>#include <mpi.h>#define  TRUE 1 /*	* 函數名: main	* 功能：實現快速排序的主程序	* 輸入：argc為命令行參數個數；	*       argv為每個命令行參數組成的字符串數組。	* 輸出：返回0代表程序正常結束*/main(int argc,char *argv[]){	int DataSize;	int *data;	/*MyID表示進程標志符；SumID表示組內進程數*/	int	MyID, SumID;	int i, j;	int m, r;	MPI_Status status;	/*啟動MPI計算*/	MPI_Init(&argc,&argv);	/*MPI_COMM_WORLD是通信子*/	/*確定自己的進程標志符MyID*/	MPI_Comm_rank(MPI_COMM_WORLD,&MyID);		/*組內進程數是SumID*/	MPI_Comm_size(MPI_COMM_WORLD,&SumID);			/*根處理機(MyID=0)獲取必要信息，并分配各處理機進行工作*/	if(MyID==0)	{		/*獲取待排序數組的長度*/		DataSize=GetDataSize();		data=(int *)malloc(DataSize*sizeof(int));		/*內存分配錯誤*/		if(data==0) 			ErrMsg("Malloc memory error!");		/*動態生成待排序序列*/		srand(396);		for(i=0;i<DataSize;i++)		{			data[i]=(int)rand();			printf("%10d",data[i]);		}		printf("\n");	}	m=log2(SumID);	/* 從根處理器將數據序列廣播到其他處理器*/	/*{"1"表示傳送的輸入緩沖中的元素的個數,	   */	/* "MPI_INT"表示輸入元素的類型,			   */ 	/* "0"表示root processor的ID  }			   */	MPI_Bcast(&DataSize,1,MPI_INT,0,MPI_COMM_WORLD);		/*ID號為0的處理器調度執行排序*/	para_QuickSort(data,0,DataSize-1,m,0,MyID);    	/*ID號為0的處理器打印排序完的有序序列*/	if(MyID==0)	{		for(i=0;i<DataSize;i++)		{			printf("%10d",data[i]);		}		printf("\n");	}	MPI_Finalize();		//結束計算}/*	* 函數名: para_QuickSort	* 功能：并行快速排序，對起止位置為start和end的序列，使用2的m次冪個處理器進行排序	* 輸入：無序數組data[1,n]，使用的處理器個數2^m	* 輸出：有序數組data[1,n]*/para_QuickSort(int *data,int start,int end,int m,int id,int MyID){	int i, j;	int r;	int MyLength;	int *tmp;	MPI_Status status;	MyLength=-1;	/*如果可供選擇的處理器只有一個，那么由處理器id調用串行排序，對應于算法13.4步驟(1.1)*/	/*(1.1)	Pid call quicksort(data,i,j) */	if(m==0)	{		if(MyID==id)			QuickSort(data,start,end);		return;	}		/*由第id號處理器劃分數據，并將后一部分數據發送到處理器id+exp2(m-1)，對應于算法13.4步驟(1.2,1.3)*/	/*(1.2) Pid: r=patrition(data,i,j)*/		if(MyID==id)	{		/*將當前的無序區R[1，n]劃分成左右兩個無序的子區R[1，i-1]和R[i，n](1≤i≤n)*/		r=Partition(data,start,end);			MyLength=end-r;			/*(1.3)	Pid send data[r+1,m-1] to P(id+2m-1) */		/* {MyLength表示發送緩沖區地址；*/		/*  發送元素數目為1;		   */		/*  MyID是消息標簽 }		   */		MPI_Send(&MyLength,1,MPI_INT,id+exp2(m-1),MyID,MPI_COMM_WORLD);		/*若緩沖區不空，則第id+2m-1號處理器取數據的首址是data[r+1]*/		if(MyLength!=0)			MPI_Send(data+r+1,MyLength,MPI_INT,id+exp2(m-1),MyID,MPI_COMM_WORLD);	}	/*處理器id+exp2(m-1)接受處理器id發送的消息*/	if(MyID==id+exp2(m-1))	{		MPI_Recv(&MyLength,1,MPI_INT,id,id,MPI_COMM_WORLD,&status);		if(MyLength!=0)		{			tmp=(int *)malloc(MyLength*sizeof(int));			if(tmp==0) ErrMsg("Malloc memory error!");			MPI_Recv(tmp,MyLength,MPI_INT,id,id,MPI_COMM_WORLD,&status);		}	}	/*遞歸調用并行排序，對應于算法13.4步驟(1.4，1.5)*/	/*用2^m-1個處理器對start--(r-1)的數據進行遞歸排序*/	j=r-1-start;		MPI_Bcast(&j,1,MPI_INT,id,MPI_COMM_WORLD);	/*(1.4)	para_quicksort(data,i,r-1,m-1,id)*/	if(j>0)		para_QuickSort(data,start,r-1,m-1,id,MyID);	/*用2^m-1個處理器對(r+1)--end的數據進行遞歸排序*/	j=MyLength;		MPI_Bcast(&j,1,MPI_INT,id,MPI_COMM_WORLD);	/*(1.5)	para_quicksort(data,r+1,j,m-1,id+2m-1)*/	if(j>0)		para_QuickSort(tmp,0,MyLength-1,m-1,id+exp2(m-1),MyID);	/*將排序好的數據由處理器id+exp2(m-1)發回id號處理器，對應于算法13.4步驟(1.6)*/	/*(1.6)	P(id+2m-1) send data[r+1,m-1] back to Pid */	if((MyID==id+exp2(m-1)) && (MyLength!=0))		MPI_Send(tmp,MyLength,MPI_INT,id,id+exp2(m-1),MPI_COMM_WORLD);	if((MyID==id) && (MyLength!=0))		MPI_Recv(data+r+1,MyLength,MPI_INT,id+exp2(m-1),id+exp2(m-1),MPI_COMM_WORLD,&status);}/*	* 函數名: QuickSort	* 功能：對起止位置為start和end的數組序列，進行串行快速排序。	* 輸入：無序數組data[1,n]	* 返回：有序數組data[1,n]*/QuickSort(int *data,int start,int end){	int r;	int i;	if(start<end)	{		r=Partition(data,start,end);		QuickSort(data,start,r-1);		QuickSort(data,r+1,end);	}}/*	* 函數名: Partition	* 功能：對起止位置為start和end的數組序列，將其分成兩個非空子序列，	*		其中前一個子序列中的任意元素小于后個子序列的元素。	* 輸入：無序數組data[1,n]	* 返回: 兩個非空子序列的分界下標*/int Partition(int *data,int start,int end){	int pivo;	int i, j;	int tmp;	pivo=data[end];				i=start-1;				/*i(活動指針)*/	for(j=start;j<end;j++)		if(data[j]<=pivo)		{			i++;			/*i表示比pivo小的元素的個數*/			tmp=data[i];			data[i]=data[j];			data[j]=tmp;		}		tmp=data[i+1];	data[i+1]=data[end];	data[end]=tmp;			/*以pivo為分界，data[i+1]=pivo*/	return i+1;}/*	* 函數名: exp2	* 功能：求2的num次冪	* 輸入：int型數據num	* 返回: 2的num次冪*/int exp2(int num){	int i;	i=1;	while(num>0)	{		num--;		i=i*2;	}		return i;}/*	* 函數名: log2	* 功能：求以2為底的num的對數	* 輸入：int型數據num	* 返回: 以2為底的num的對數*/int log2(int num){	int i, j;	i=1;		j=2;	while(j<num)	{		j=j*2;		i++;	}	if(j>num)		i--;	return i;}/*	* 函數名: GetDataSize	* 功能：讀入待排序序列長度*/int GetDataSize(){	int i;	while(TRUE)	{		printf("Input the Data Size :");		scanf("%d",&i);		/*讀出正確的i，返回；否則，繼續要求輸入*/		if((i>0) && (i<=65535))					break;		ErrMsg("Wrong Data Size, must between [1..65535]");	}	return i;}/*輸出錯誤信息*/ErrMsg(char *msg){	printf("Error: %s \n",msg);}