#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）