并行快速排序

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

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

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

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

int partition(int* array, int left, int right)
{
        int index = left;
        int pivot = array[index];
        swap(array[index], array[right]);
        for (int i=left; i<right; i++)
        {
                if (array[i] > pivot)    // 降序
                        swap(array[index++], array[i]);
        }
        swap(array[right], array[index]);
        return index;
}

void qsort(int* array, int left, int right)
{
        if (left >= right)
                return;
        int index = partition(array, left, right);
        qsort(array, left, index - 1);
        qsort(array, index + 1, right);
}

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


template <typename key, typename container >void parallel_sort(container & _container)template <typename key, typename container >
void partition_less(std::vector<key> * vless, container * _container, key privot){
for(size_t i = 0; i < (*_container).size(); i++){
        if ((*_container)[i] < privot){
            vless->push_back((*_container)[i]);
        }
    }
}

template <typename key,  typename container >
void partition_more(std::vector<key> * vmore, container * _container, key privot){
for(size_t i = 0; i < (*_container).size(); i++){
        if ((*_container)[i] >= privot){
            vmore->push_back((*_container)[i]);
        }
    }
}

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

template <typename key, typename container >
int sort_less(container * _container, std::vector<key> & vless, boost::atomic_uint32_t * depth){
    parallel_sort_impl<key>(&vless, *depth);

    for(size_t i = 0; i < vless.size(); i++){
        (*_container)[i] = vless[i];
    }

    return 0;
}

template <typename key, typename container >
int sort_more(container * _container, std::vector<key> & vmore, boost::atomic_uint32_t * depth){
    parallel_sort_impl<key>(&vmore, *depth);

    size_t pos = (*_container).size()-vmore.size();
    for(size_t i = 0; i < vmore.size(); i++){
        (*_container)[i+pos] = vmore[i];
    }

    return 0;
}

template <typename key, typename container >
void parallel_sort_impl(container * _container, boost::atomic_uint32_t & depth){
    if (_container->size() < threshold || depth.load() > processors_count()){
        std::sort(_container->begin(), _container->end());
    }else{
        key privot = (*_container)[_container->size()/2];

    std::vector<key> vless, vmore;
    auto partition_result = std::async(std::launch::async, partition_less<key, container>, &vless, _container, privot);
    partition_more(&vmore, _container, privot);
    partition_result.get();

        auto result = std::async(std::launch::async, sort_less<key, container>, _container, vless, &depth);
        sort_more(_container, vmore, &depth);
        result.get();
    }
}

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

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

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 并行快速排序



浅水清流

本人的新浪微博是http://weibo.com/u/1913446335,本人的QQ:451517996,个人博客:http://www.cnblogs.com/qianqians/。希望和大家多交流。

Latest posts by 浅水清流 (see all)

FavoriteLoading添加本文到我的收藏
  • Trackback are closed
  • Comments (1)
    • lmxeq5
    • 05/06. 2014 4:11pm

    还有一种方案:直接将待排序数组分成两部分,然后对每个部分并行的快速排序,排完之后再用一个线程对两部分进行归并

You must be logged in to post a comment.

return top