首页 > 代码库 > OpenMP之枚举排序
OpenMP之枚举排序
// EnumSort.cpp : 定义控制台应用程序的入口点。 //枚举排序 /* 枚举排序(Enumeration Sort)是一种最简单的排序算法,通常也称为秩排序(Rank Sort)。 该算法的具体思想是(假设按关键字递增排序),对每一个待排序的元素统计小于它的所有元素的个数,从而得到该元素最终处于序列中的位置。 假定待排序的n个数存在a[1]…a[n]中。首先将a[1]与a[2]…a[n]比较,记录比其小的数的个数,令其为k, a[1]就被存入有序的数组b[1]…b[n]的b[k+1]位置上;然后将a[2]与a[1],a[3]…a[n]比较,记录比其小的数的个数,依此类推。 这样的比较操作共n(n-1)次,所以串行秩排序的时间复杂度为O(n2)。 */ #include "stdafx.h" #include <Windows.h> #include <omp.h> #include <time.h> #include <iostream> using namespace std; #define NUM_THREADS 2 #define maxN 100000 int _tmain(int argc, _TCHAR* argv[]) { int i,j,k; clock_t t1,t2; omp_set_num_threads(NUM_THREADS); int a[maxN];//={0,4,9,6,1,5,3,8,7,2}; int b[maxN]; //并行——————————; for (i=0;i<maxN;i++) { a[i]=maxN-i; } t1=clock(); #pragma omp parallel sections private(i,j,k) { /*#pragma omp for for (i=0;i<maxN;i++) { k=0; for (j=0;j<maxN;j++) { if (a[i]>a[j]) { k++; } } b[k]=a[i]; }*/ #pragma omp section { for (i=omp_get_thread_num();i<maxN;i=i+NUM_THREADS) { k=0; for (j=0;j<maxN;j++) { if (a[i]>a[j])//找出数组中比自己小的元素的个数k; { k++; } } b[k]=a[i];//另外建立一个数组,将其放到第k+1处; } } #pragma omp section { for (i=omp_get_thread_num();i<maxN;i=i+NUM_THREADS) { k=0; for (j=0;j<maxN;j++) { if (a[i]>a[j]) { k++; } } b[k]=a[i]; } } } t2=clock(); cout<<"并行时间:"<<t2-t1<<endl; for (i=99900;i<maxN;i++) { cout<<b[i]<<" "; } cout<<endl; //串行————————————; for (i=0;i<maxN;i++) { a[i]=maxN-i; } t1=clock(); for (i=0;i<maxN;i++) { k=0; for (j=0;j<maxN;j++) { if (a[i]>a[j]) { k++; } } b[k]=a[i]; } t2=clock(); cout<<"串行时间:"<<t2-t1<<endl; for (i=99900;i<maxN;i++) { cout<<b[i]<<" "; } cout<<endl; system("pause"); return 0; }
运行结果如下图:(相对加速比:1.72)
OpenMP之枚举排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。