count_sort计数排序OpenMP的并行化

灰太狼 2022-04-03 09:16 220阅读 0赞

## 简述 ##

计数排序，就是统计某个数值在所有的数字中所应该存在的位置，然后，放到一个确定的位置上。非常简单的排序算法。

## 程序 ##

*  会读取data.txt中的文件
 *  数据的样子

10 
    0 2 3 1 4 8 6 7 5 9

*  效果

PS D:\C++\VS\repo\OpenMP-TEST\Debug> ./OpenMP-TEST
    0 1 2 3 4 5 6 7 8 9

*  代码

#include <iostream>
    #include <omp.h>
    #include <fstream>
    using namespace std;
    #pragma warning(disable : 4996)
    int main(int argc, char **argv) { 
    	if (argc < 1) return 0;
    	ifstream cin("./data.txt");
    	int i, j, count, n;
    	cin >> n;
    	int *a = new int[n];
    	int *temp = new int[n];
    	
    	//int thread_count = strtol(argv[1], NULL, 10);
    	for (i = 0; i < n; ++i)  cin >> a[i];
    
    #pragma omp parallel for private(i, j, count) shared(n, a, temp)
    	for (i = 0; i < n; ++i) { 
    		count = 0;
    		for (j = 0; j < n; ++j) { 
    			if (a[j] < a[i]) count++;
    			else if (a[j] == a[i] && j < i) count++;
    		}
    		temp[count] = a[i];
    	}
    
    #pragma omp parallel for 
    	for (i = 0; i < n; ++i) a[i] = temp[i];
    
    	for (i = 0; i < n; ++i) cout << a[i]<< " ";
    	cout << endl;
    
    	delete[]temp;
    	delete[]a;
    }

### 和串行的计数排序进行对比 ###

*  不要输出排序结果，因为数据量太大了。
 *  10000个数据的排序效果

PS D:\C++\VS\repo\OpenMP-TEST\Debug> ./OpenMP-TEST r
    Total time Serial: 1.256s
    Total time parallel: 0.141s

*  接近9倍的速度（因为我在笔记本上有8个核）
 *  后面多了一个r命令，其实是免得在vs编译的时候被调用。随便写什么都是ok的。

#include <iostream>
    #include <omp.h>
    #include <fstream>
    #include <ctime>
    using namespace std;
    #pragma warning(disable : 4996)
    int main(int argc, char **argv) { 
    	if (argc < 2) return 0;
    	ifstream cin("./data.txt");
    	int i, j, count, n;
    	cin >> n;
    	int *a = new int[n];
    	int *b = new int[n];
    	int *temp = new int[n];
    	
    	//int thread_count = strtol(argv[1], NULL, 10);
    	for (i = 0; i < n; ++i) cin >> b[i];
    	for (i = 0; i < n; ++i) a[i] = b[i];
    	
    	clock_t starttime, endtime;
    	starttime = clock();
    	for (i = 0; i < n; ++i) { 
    		count = 0;
    		for (j = 0; j < n; ++j) { 
    			if (b[j] < b[i]) count++;
    			else if (b[j] == b[i] && j < i) count++;
    		}
    		temp[count] = b[i];
    	}
    	memcpy(b, temp, n * sizeof(int));
    	endtime = clock();
    
    	// for (i = 0; i < n; ++i) cout << b[i] << " ";
    	// cout << endl;
    	cout << "Total time Serial: " << (double)(endtime - starttime) / CLOCKS_PER_SEC << "s" << endl;
    
    	starttime = clock();
    #pragma omp parallel for private(i, j, count) shared(n, a, temp)
    	for (i = 0; i < n; ++i) { 
    		count = 0;
    		for (j = 0; j < n; ++j) { 
    			if (a[j] < a[i]) count++;
    			else if (a[j] == a[i] && j < i) count++;
    		}
    		temp[count] = a[i];
    	}
    
    #pragma omp parallel for 
    	for (i = 0; i < n; ++i) a[i] = temp[i];
    
    	endtime = clock();
    
    	//for (i = 0; i < n; ++i) cout << a[i]<< " ";
    	//cout << endl;
    	cout << "Total time parallel: " << (double)(endtime - starttime) / CLOCKS_PER_SEC << "s" << endl;
    	delete[]temp;
    	delete[]a;
    	delete[]b;
    }

### 和qsort的串行版也做对比 ###

![在这里插入图片描述][20181221150137118.png]

#include <iostream>
    #include <omp.h>
    #include <fstream>
    #include <ctime>
    using namespace std;
    #pragma warning(disable : 4996)
    int cmp(const void * a, const void *b) //from small to big
    { 
    	return *(int *)a - *(int *)b;
    }
    
    int main(int argc, char **argv) { 
    	if (argc < 2) return 0;
    	ifstream cin("./data.txt");
    	int i, j, count, n;
    	cin >> n;
    	int *a = new int[n];
    	int *b = new int[n];
    	int *c = new int[n];
    	int *temp = new int[n];
    	
    	//int thread_count = strtol(argv[1], NULL, 10);
    	for (i = 0; i < n; ++i) cin >> b[i];
    	for (i = 0; i < n; ++i) {  a[i] = b[i]; c[i] = b[i]; }
    	
    
    	clock_t starttime, endtime;
    	starttime = clock();
    	qsort(c, n, sizeof(int), cmp);
    	endtime = clock();
    	cout << "Total time Serial-qsort: " << (double)(endtime - starttime) / CLOCKS_PER_SEC << "s" << endl;
    
    	starttime = clock();
    	for (i = 0; i < n; ++i) { 
    		count = 0;
    		for (j = 0; j < n; ++j) { 
    			if (b[j] < b[i]) count++;
    			else if (b[j] == b[i] && j < i) count++;
    		}
    		temp[count] = b[i];
    	}
    	memcpy(b, temp, n * sizeof(int));
    	endtime = clock();
    	cout << "Total time Serial: " << (double)(endtime - starttime) / CLOCKS_PER_SEC << "s" << endl;
    
    	starttime = clock();
    #pragma omp parallel for private(i, j, count) shared(n, a, temp)
    	for (i = 0; i < n; ++i) { 
    		count = 0;
    		for (j = 0; j < n; ++j) { 
    			if (a[j] < a[i]) count++;
    			else if (a[j] == a[i] && j < i) count++;
    		}
    		temp[count] = a[i];
    	}
    
    #pragma omp parallel for 
    	for (i = 0; i < n; ++i) a[i] = temp[i];
    
    	endtime = clock();
    
    	//for (i = 0; i < n; ++i) cout << a[i]<< " ";
    	//cout << endl;
    	cout << "Total time parallel: " << (double)(endtime - starttime) / CLOCKS_PER_SEC << "s" << endl;
    	delete[]temp;
    	delete[]a;
    }

[20181221150137118.png]: /images/20220403/076c83ed62694913afafafcc5d26349c.png