并行快速排序_并行快速排序算法代码-程序员宅基地

技术标签： 算法  快速排序  

并行快速排序

感谢网友浅水清流投递本稿。

并发算法是多核时代开始流行的技术趋势，比如tbb，ppl都提供了大量有用的并发算法。

经典算法中，排序是一个很适合采用分治法并发的场合，比如快速排序。

常规的快速排序，先在数组中选取一个基准点，将数组分区为小于基准点和大于基准点（相同的数可以到任一边），对分区的子数组递归的执行分区的操作，当子数组长度为1时退出递归。此时数组就完成了排序过程。

01 int partition(int* array, int left, int right)
02 {
03         int index = left;
04         int pivot = array[index];
05         swap(array[index], array[right]);
06         for (int i=left; i<right; i++)
07         {
08                 if (array[i] > pivot)    // 降序
09                         swap(array[index++], array[i]);
10         }
11         swap(array[right], array[index]);
12         return index;
13 }
14  
15 void qsort(int* array, int left, int right)
16 {
17         if (left >= right)
18                 return;
19         int index = partition(array, left, right);
20         qsort(array, left, index - 1);
21         qsort(array, index + 1, right);
22 }

对快排的过程分析可以发现，分区以及对子数组排序的过程均可以并发执行，这里首先对数组进行分区，生成分区数组，为了保证不同分区不受到影响需要先完成分区再进行排序。

01 template <typename key, typename container >void parallel_sort(container & _container)template <typename key, typename container >
02 void partition_less(std::vector<key> * vless, container * _container, key privot){
03 for(size_t i = 0; i < (*_container).size(); i++){
04         if ((*_container)[i] < privot){
05             vless->push_back((*_container)[i]);
06         }
07     }
08 }
09  
10 template <typename key,  typename container >
11 void partition_more(std::vector<key> * vmore, container * _container, key privot){
12 for(size_t i = 0; i < (*_container).size(); i++){
13         if ((*_container)[i] >= privot){
14             vmore->push_back((*_container)[i]);
15         }
16     }
17 }

在完成分区之后，递归执行排序操作，并将排序好的分区重新写入待排序数组。

01 template <typename key, typename container >
02 int sort_less(container * _container, std::vector<key> & vless, boost::atomic_uint32_t * depth){
03     parallel_sort_impl<key>(&vless, *depth);
04  
05     for(size_t i = 0; i < vless.size(); i++){
06         (*_container)[i] = vless[i];
07     }
08  
09     return 0;
10 }
11  
12 template <typename key, typename container >
13 int sort_more(container * _container, std::vector<key> & vmore, boost::atomic_uint32_t * depth){
14     parallel_sort_impl<key>(&vmore, *depth);
15  
16     size_t pos = (*_container).size()-vmore.size();
17     for(size_t i = 0; i < vmore.size(); i++){
18         (*_container)[i+pos] = vmore[i];
19     }
20  
21     return 0;
22 }
23  
24 template <typename key, typename container >
25 void parallel_sort_impl(container * _container, boost::atomic_uint32_t & depth){
26     if (_container->size() < threshold || depth.load() > processors_count()){
27         std::sort(_container->begin(), _container->end());
28     }else{
29         key privot = (*_container)[_container->size()/2];
30  
31     std::vector<key> vless, vmore;
32     auto partition_result = std::async(std::launch::async, partition_less<key, container>, &vless, _container, privot);
33     partition_more(&vmore, _container, privot);
34     partition_result.get();
35  
36         auto result = std::async(std::launch::async, sort_less<key, container>, _container, vless, &depth);
37         sort_more(_container, vmore, &depth);
38         result.get();
39     }
40 }

这里采取了一个有趣的策略，就是通过数组的大小，计算出排序好的元素在原数组中的位置（这样即使是并发的访问数组，但是因为不同的线程各自访问的自己的下标位置，所以仍然是线程安全的），然后将排序好的数组直接写入到原数组，完成整个排序。

这里的并发采用了c++11中的promise:http://imcc.blogbus.com/logs/174131661.html

（全文完）如果您喜欢此文请点赞，分享，评论。
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/yipiankongbai/article/details/23276711

智能推荐

Nginx，nginx-rtmp-module-master搭建直播平台-程序员宅基地

文章浏览阅读511次。Nginx，nginx-rtmp-module-master搭建直播平台_nginx-rtmp-module-master

**The sip module implements API v11.0 to v11.2 but the PyQt5.QtCore module requires API v11.3**_the pyqt5.qtcore module failed to register with th-程序员宅基地

文章浏览阅读3.6k次。*The sip module implements API v11.0 to v11.2 but the PyQt5.QtCore module requires API v11.3*情况一 SIP版本不匹配我在使用PyQt5时遇到了这个问题：“sip模块实现了API v11.0到v11.2，但PyQt5.QtWidgets模块需要API v11.3”pip列表sip 4.18，但是使..._the pyqt5.qtcore module failed to register with the sip module

Lesson1强化学习（RL）初印象 学习笔记_rl编程-程序员宅基地

文章浏览阅读467次。Lesson1强化学习（RL）初印象_rl编程

mysql存储过程执行返回-1_mysql简单存储过程创建并返回执行结果-程序员宅基地

文章浏览阅读825次。DROP PROCEDURE IF EXISTS `create_appeal`;DELIMITER $$CREATE PROCEDURE `create_appeal`(IN userId INT,IN userName VARCHAR(20),IN historyId VARCHAR(20),IN productId INT,IN tourneyId INT,IN roundId TINY..._mysql8 创建存储过程返回 -1

过滤器防止xss攻击_xss过滤器-程序员宅基地

文章浏览阅读950次。将参数中有关xss攻击的非法字符全部处理掉。_xss过滤器

最美纪念日-程序员宅基地

文章浏览阅读58次。有问题请留言：[email protected]

随便推点

3 cmake-生成dll和lib_cmake生成dll和lib文件-程序员宅基地

文章浏览阅读8.9k次。1 工程目录最顶层的CMakeList.txt添加add_subdirectory (CMakeLibDemo)add_subdirectory (CMakeLibDemoUse)2 文件ALU.h#pragma once#define DllExport __declspec( dllexport )//宏定义#ifndef ALU_H #define ALU_H #include <iostream> using namespace std;class Dll_cmake生成dll和lib文件

vector和map的效率简要比较_map和vector区别 效率-程序员宅基地

文章浏览阅读2w次，点赞7次，收藏21次。项目中要对一些数据结构进行存取，而项目本身对时间延时比较敏感，在使用vector还是map上着实纠结了一番，主要某些数据量比较小，才有此纠结。而且想搞明白，到底大到什么数据量该用map？做了一些简单的测试，见下。首先，不管是vector还是map，请尽量存取指针，否则在存取时会有拷贝带来不必要的时间损失。通常用int和string做key的场景比较普遍（我的项目即如此），能用int_map和vector区别 效率

今日做题家 - 面试算法题教程系列总纲，web开发难点-程序员宅基地

文章浏览阅读760次，点赞16次，收藏27次。基于大部分计算机行业从业者都没有信息竞赛学的经验，比如 NOIP、NOI、ACM 之类的，而目前国内外的大厂算法题、系统设计题之类的考察却又必不可少（这里不会去论证面试进行算法考察的优缺点，只从适应规则的角度来讲），以至于大家看到算法面试题都会慌。

巨人网络李东旭：关于提高游戏流畅性的那些事_球球大作战李东旭-程序员宅基地

文章浏览阅读275次。程序员的噩梦，一定是某个角落突然有人大呼“怎么又这么卡呀？？？”玩家、运营、产品老是喷你的客户端为什么卡怎么办？总有些技巧，学会了，卡顿的锅，咱技术不背！李东旭巨人网络客户端软件专家。擅长含有物理、数学等游戏玩法研发，熟悉游戏性能优化，目前负责《球球大作战》客户端相关研发。本期Live，GAD邀请到了巨人网络客户端资深软件工程师李东旭老师，以《球球大作战》为例，分享了手游客户端的优化技巧、客户端与服务器的同步怎么优化等问题，干货满满，小编本着有福同享的原则整理了Live的精彩内容推送给大家。1.我们一个.._球球大作战李东旭

broyden matlab,broyden方法求解非线性方程组的matlab实现-程序员宅基地

文章浏览阅读809次。broyden方法求解非线性方程组的matlab实现 Broyden 方法求解非线性方程组的 Matlab 实现注：matlab 代码来自网络，仅供学习参考。 1. 把以下代码复制在一个.m 文件上 function [sol, it_hist, ierr] = brsola(x,f,tol, parms) % Broyden s solver, globally convergent % sol..._broyden算法代码

基于matlab+模板匹配的车牌识别_255 * mx / (xmax - xmin)-程序员宅基地

文章浏览阅读3.2w次，点赞51次，收藏422次。一、前言 随着我国经济的快速发展，汽车拥有量的急剧增加，公路交通成为我国重要的交通运输途径，是国家大力发展的基础设施之一。因此，交通管理的现代化和智能化就越来越显得重要和亟迫。利用电子信息技术来提高管理效率、交通效率和打造安全的智能交通系统已成为当前交通管理发展的主题。实现交通管理现代化和智能化的核心技术之一就是车牌自动识别技术。与传统的车辆管理方法相比，它大大提高了管理效率和水平..._255 * mx / (xmax - xmin)

推荐文章

热门文章

相关标签