首页 > 代码库 > QuickSort (MPI 实现)

QuickSort (MPI 实现)

2024-08-06 10:16:51   222人阅读

 //
 #include "stdafx.h"
 #include"mpi.h"
 #include<iostream>
 #include <stdlib.h>
 #include <stdio.h>
 using namespace std;
 #define TRUE 1
 /*
 * 函数名: Partition
 * 功能：对起止位置为wht_start和wht_end的数组序列，将其分成两个非空子序列，
 * 其中前一个子序列中的任意元素小于后个子序列的元素。
 * 输入：无序数组wht_data[1,n]
 * 返回: 两个非空子序列的分界下标
 */
 double wht_start_time,wht_end_time;
 int Partition(int *wht_data,int wht_start,int wht_end)
 {
 int wht_pivo;
 int wht_i, wht_j;
 int wht_tmp;
 wht_pivo=wht_data[wht_end];
 wht_i=wht_start-1; /*wht_i(活动指针)*/
  
 for(wht_j=wht_start;wht_j<wht_end;wht_j++)
 if(wht_data[wht_j]<=wht_pivo)
 {
 wht_i++; /*wht_i表示比wht_pivo小的元素的个数*/
 wht_tmp=wht_data[wht_i];
 wht_data[wht_i]=wht_data[wht_j];
 wht_data[wht_j]=wht_tmp;
 }
 wht_tmp=wht_data[wht_i+1];
 wht_data[wht_i+1]=wht_data[wht_end];
 wht_data[wht_end]=wht_tmp; /*以wht_pivo为分界，wht_data[wht_i+1]=wht_pivo*/
 return wht_i+1;
 }
 /*
 * 函数名: QuickSort
 * 功能：对起止位置为wht_start和wht_end的数组序列，进行串行快速排序。
 * 输入：无序数组wht_data[1,n]
 * 返回：有序数组wht_data[1,n]
 */
 void QuickSort(int *wht_data,int wht_start,int wht_end)
 {
 int wht_r;
 int wht_i;
 if(wht_start<wht_end)
 {
 wht_r=Partition(wht_data,wht_start,wht_end);
 QuickSort(wht_data,wht_start,wht_r-1);
 QuickSort(wht_data,wht_r+1,wht_end);
 }
 }
 /*
 * 函数名: exp2
 * 功能：求2的wht_num次幂
 * 输入：int型数据wht_num
 * 返回: 2的wht_num次幂
 */
 int exp2(int wht_num)
 {
 int wht_i;
 wht_i=1;
 while(wht_num>0)
 {
 wht_num--;
 wht_i=wht_i*2;
 }
 return wht_i;
 }
 /*
 * 函数名: log2
 * 功能：求以2为底的wht_num的对数
 * 输入：int型数据wht_num
 * 返回: 以2为底的wht_num的对数
 */
 int log2(int wht_num)
 {
 int wht_i, wht_j;
 wht_i=1;
 wht_j=2;
 while(wht_j<wht_num)
 {
 wht_j=wht_j*2;
 wht_i++;
 }
 if(wht_j>wht_num)
 wht_i--;
 return wht_i;
 }
  
 /*
 * 函数名: Getwht_dataSize
 * 功能：读入待排序序列长度
 */
 int Getwht_dataSize()
 {
 double wht_i;
 while(TRUE)
 {
 printf("请输入生成的随机数的个数（范围[900000~1000000]） :");
 fflush(stdout);
 //scanf("%d",&wht_i);
 cin>>wht_i;
 /*读出正确的wht_i，返回；否则，继续要求输入*/
 if((wht_i>=900000) && (wht_i<=1000000))
 break;
 printf("输入错误,数字范围是 [900000~1000000]");
 printf("\n");
 }
 return wht_i;
 }
  
 /*
 * 函数名: para_QuickSort
 * 功能：并行快速排序，对起止位置为wht_start和wht_end的序列，使用2的wht_m次幂个处理器进行排序
 * 输入：无序数组wht_data[1,n]，使用的处理器个数2^wht_m
 * 输出：有序数组wht_data[1,n]
 */
 void para_QuickSort(int *wht_data,int wht_start,int wht_end,int wht_m,int id,int MyID)
 {
 int wht_i, wht_j;
 int wht_r;
 int MyLength;
 int *wht_tmp;
 MPI_Status status;
 MyLength=-1;
 /*如果可供选择的处理器只有一个，那么由处理器id调用串行排序，对应于算法13.4步骤(1.1)*/
 /*(1.1) Pid call quicksort(wht_data,wht_i,wht_j) */
 if(wht_m==0)
 {
 wht_start_time=MPI_Wtime();
 if(MyID==id)
 QuickSort(wht_data,wht_start,wht_end);
 return;
 }
 wht_start_time=MPI_Wtime();
 /*由第id号处理器划分数据，并将后一部分数据发送到处理器id+exp2(wht_m-1)，对应于算法步骤(1.2,1.3)*/
 /*(1.2) Pid: wht_r=patrition(wht_data,wht_i,wht_j)*/
 if(MyID==id)
 {
 /*将当前的无序区R[1，n]划分成左右两个无序的子区R[1，wht_i-1]和R[wht_i，n](1≤wht_i≤n)*/
 wht_r=Partition(wht_data,wht_start,wht_end);
 MyLength=wht_end-wht_r;
 /*(1.3) Pid swht_end wht_data[wht_r+1,wht_m-1] to P(id+2m-1) */
 /* {MyLength表示发送缓冲区地址；*/
 /* 发送元素数目为1; */
 /* MyID是消息标签 } */
 MPI_Send(&MyLength,1,MPI_INT,id+exp2(wht_m-1),MyID,MPI_COMM_WORLD);
 /*若缓冲区不空，则第id+2m-1号处理器取数据的首址是wht_data[wht_r+1]*/
 if(MyLength!=0)
 MPI_Send(wht_data+wht_r+1,MyLength,MPI_INT,id+exp2(wht_m-1),MyID,MPI_COMM_WORLD);
 }
 /*处理器id+exp2(wht_m-1)接受处理器id发送的消息*/
 if(MyID==id+exp2(wht_m-1))
 {
 MPI_Recv(&MyLength,1,MPI_INT,id,id,MPI_COMM_WORLD,&status);
 if(MyLength!=0)
 {
 wht_tmp=(int *)malloc(MyLength*sizeof(int));
 if(wht_tmp==0) printf("Malloc memory error!");
 MPI_Recv(wht_tmp,MyLength,MPI_INT,id,id,MPI_COMM_WORLD,&status);
 }
 }
 /*递归调用并行排序，对应于算法(1.4，1.5)*/
 /*用2^wht_m-1个处理器对wht_start--(wht_r-1)的数据进行递归排序*/
 wht_j=wht_r-1-wht_start;
 MPI_Bcast(&wht_j,1,MPI_INT,id,MPI_COMM_WORLD);
 /*(1.4) para_quicksort(wht_data,wht_i,wht_r-1,wht_m-1,id)*/
 if(wht_j>0)
 para_QuickSort(wht_data,wht_start,wht_r-1,wht_m-1,id,MyID);
 /*用2^wht_m-1个处理器对(wht_r+1)--wht_end的数据进行递归排序*/
 wht_j=MyLength;
 MPI_Bcast(&wht_j,1,MPI_INT,id,MPI_COMM_WORLD);
 /*(1.5) para_quicksort(wht_data,wht_r+1,wht_j,wht_m-1,id+2m-1)*/
 if(wht_j>0)
 para_QuickSort(wht_tmp,0,MyLength-1,wht_m-1,id+exp2(wht_m-1),MyID);
 /*将排序好的数据由处理器id+exp2(wht_m-1)发回id号处理器，对应于算法/
 /*(1.6) P(id+2m-1) swht_end wht_data[wht_r+1,wht_m-1] back to Pid */
 if((MyID==id+exp2(wht_m-1)) && (MyLength!=0))
 MPI_Send(wht_tmp,MyLength,MPI_INT,id,id+exp2(wht_m-1),MPI_COMM_WORLD);
 if((MyID==id) && (MyLength!=0))
 MPI_Recv(wht_data+wht_r+1,MyLength,MPI_INT,id+exp2(wht_m-1),id+exp2(wht_m-1),MPI_COMM_WORLD,&status);
 }
 /*
 * 函数名: main
 * 功能：实现快速排序的主程序
 * 输入：argc为命令行参数个数；
 * argv为每个命令行参数组成的字符串数组。
 * 输出：返回0代表程序正常结束
 */
 int main(int argc,char *argv[])
 {
 double wht_dataSize;
 int *wht_data;
 /*MyID表示进程标志符；SumID表示组内进程数*/
 int MyID, SumID;
 int wht_i, wht_j;
 int wht_m, wht_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)
 {
 /*获取待排序数组的长度*/
 wht_dataSize=Getwht_dataSize();
 wht_data=http://www.mamicode.com/(int *)malloc(wht_dataSize*sizeof(int));
  
 /*内存分配错误*/
 if(wht_data=http://www.mamicode.com/=0)
 printf("Malloc memory error!");
  
 /*动态生成待排序序列*/
 srand(396);
 //printf("排序前的随机数组为 :\n");
 for(wht_i=0;wht_i<wht_dataSize;wht_i++)
 {
 wht_data[wht_i]=(int)rand();
 // printf("%10d",wht_data[wht_i]);
 }
 printf("\n");
 }
 wht_m=log2(SumID);
 /* 从根处理器将数据序列广播到其他处理器*/
 /*{"1"表示传送的输入缓冲中的元素的个数, */
 /* "MPI_INT"表示输入元素的类型, */
 /* "0"表示root processor的ID } */
 MPI_Bcast(&wht_dataSize,1,MPI_INT,0,MPI_COMM_WORLD);
 /*ID号为0的处理器调度执行排序*/
 para_QuickSort(wht_data,0,wht_dataSize-1,wht_m,0,MyID);
 wht_end_time=MPI_Wtime();
 /*ID号为0的处理器打印排序完的有序序列*/
 if(MyID==0)
 {
 //printf("排序后的有序数组为 :\n");
 //for(wht_i=0;wht_i<wht_dataSize;wht_i++)
 //{
 // printf("%10d",wht_data[wht_i]);
 //}
 printf("\n");
 printf("Time=%f\n",wht_end_time-wht_start_time);
 }
  
 MPI_Finalize(); //结束计算
 }

QuickSort (MPI 实现)


联系
我们