并行计算实验快速排序的并行算法.docx

文档介绍：华南师范大学实验报告
学生姓名 学 号
专 业计算机科学与技术年级、班级
课程名称 并行计算 实验项目 快速排序的并行算法
实验类型□验证□设计□综合实验时间2010年5月10日 实验指导老味 实验评分
3・1实验目的与要求形成一个高度为logn的排序树，其计算复杂度为0 (n),通信 复杂度也为0(n)。同串行算法一样，在最坏情况下其计算复杂度降为0(n2)。正常情况下该算法的 计算复杂度也为0 (n),只不过具有更高的常数因子。
、完成快速排序的并行实现的流程图
、完成快速排序的并行算法的实现
#include <>
#include <>
#define TRUE 1
/*
* 函数名 : main
* 功能：实现快速排序的主程序
* 输入： argc 为命令行参数个数；
* argv 为每个命令行参数组成的字符串数组。
* 输出：返回 0 代表程序正常结束
*/
int GetDataSize();
para_QuickSort(int *data,int start,int end,int m,int id,int MyID);
QuickSort(int *data,int start,int end);
int Partition(int *data,int start,int end);
int exp2(int num);
int log2(int num);
ErrMsg(char *msg);
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=O)获取必要信息，并分配各处理机进行工作*/
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); //调用函数:求以 2 为底的 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)
{
printf("实际应用处理器数：％d\n ",exp2(m-l));
for(i=0;i<DataSize;i++)
{
printf("%10d",data[i]);
}
printf("\n");
}
MPI_Finalize(); //结束计算
return 0;
}/*
函数名: 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;