实现快速排序MPI并行计算

快速排序算法并行化的一个简单思想是，对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。例如对一个长为n的序列，首先划分得到两个长为n/2的序列，将其交给两个处理器分别处理；而后进一步划分得到四个长为n/4的序列，再分别交给四个处理器处理；如此递归下去最终得到排序好的序列。当然这里举的是理想的划分情况，如果划分步骤不能达到平均分配的目的，那么排序的效率会相对较差。

#include 
#include 
#include 
#define  TRUE 1
 
/*
	* 函数名: main
	* 功能：实现快速排序的主程序
	* 输入：argc为命令行参数个数；
	*       argv为每个命令行参数组成的字符串数组。
	* 输出：返回0代表程序正常结束
*/
main（int argcchar *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		{
			data[i]=（int）rand（）;
			printf（“%10d“data[i]）;
		}
		printf（“\n“）;
	}

	m=log2（SumID）;

	/* 从根处理器将数据序列广播到其他处理器*/
	/*{“1“表示传送的输入缓冲中的元素的个数	   */
	/* “MPI_INT“表示输入元素的类型			   */ 
	/* “0“表示root processor的ID  }			   */
	MPI_Bcast（&DataSize1MPI_INT0MPI_COMM_WORLD）;
	
	/*ID号为0的处理器调度执行排序*/
	para_QuickSort（data0DataSize-1m0MyID）;
    
	/*ID号为0的处理器打印排序完的有序序列*/
	if（MyID==0）
	{
		for（i=0;i		{
			printf（“%10d“data[i]）;
		}
		printf（“\n“）;
	}

	MPI_Finalize（）;		//结束计算
}


/*
	* 函数名: para_QuickSort
	* 功能：并行快速排序，对起止位置为start和end的序列，使用2的m次幂个处理器进行排序
	* 输入：无序数组data[1n]，使用的处理器个数2^m
	* 输出：有序数组data[1n]
*/
para_QuickSort（int *dataint startint endint mint idint 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（dataij） */
	if（m==0）
	{
		if（MyID==id）
			QuickSort（datastartend）;
		return;
	}	

	/*由第id号处理器划分数据，并将后一部分数据发送到处理器id+exp2（m-1），对应于算法13.4步骤（1.21.3）*/
	/*（1.2） Pid: r=patrition（dataij）*/	
	if（MyID==id）
	{
		/*将当前的无序区R[1，n]划分成左右两个无序的子区R[1，i-1]和R[i，n]（1≤i≤n）*/
		r=Partition（datastartend）;	
		MyLength=end-r;	
		/*（1.3）	Pid send data[r+1m-1] to P（id+2m-1） */
		/* {MyLength表示发送缓冲区地址；*/
		/*  发送元素数目为1;		   */
		/*  MyID是消息标签 }		   */
		MPI_Send（&MyLength1MPI_INTid+exp2（m-1）MyIDMPI_COMM_WORLD）;
		/*若缓冲区不空，则第id+2m-1号处理器取数据的首址是data[r+1]*/
		if（MyLength!=0）
			MPI_Send（data+r+1MyLengthMPI_INTid+exp2（m-1）MyIDMPI_COMM_WORLD）;
	}

	/*处理器id+exp2（m-1）接受处理器id发送的消息*/
	if（MyID==id+exp2（m-1））
	{
		MPI_Recv（&MyLength1MPI_INTididMPI_COMM_WORLD&status）;
		if（MyLength!=0）