一种基于划分与归并的并行快速排序算法

A Parallel Quicksort Algorithm Based on Partition and Merge Operations

排序作为一种计算机程序设计中的重要操作在海量数据条件下应快速且高效。而且随着当今处理器生产工艺的不断进步,如今的笔记本电脑、台式机乃至商用服务器至少也都是双核处理器,4核、8核乃至16核也并不罕见,如果是单线程的程序,那么在双核处理器上运行便浪费了50%的性能,在4核处理器上运行便浪费了75%的性能。而多核处理器上的多线程能让多段程序逻辑同时工作,可以真正发挥出多核处理器的优势,而达到充分利用处理器的目的。为了提升排序操作的性能,使用灵活的OpenMP并行函数库以及C/C++语言标准库中提供的快速排序函数qsort实现了一种可以运行于任意共享存储多核计算机上的并行快速排序算法。实验结果表明:以同条件下标准库串行快速排序函数qsort作为测试基准,最终在英特尔酷睿i7-4790处理器平台上8线程条件下对200M随机整型数据的排序将性能提升了11.92倍,在相同的数据条件下,英特尔酷睿2-Q9400处理器平台上也可将性能提升4.75倍。

As an important operation in computer programming,sorting should be faster and more efficient under big data conditions.Along with the continual progress in the modern processor production technology,laptops,desktops,and commercial servers are equipped with at least dual-core processors,and 4-core,8-core and 16-core processors are not rare any more.It is a 50%waste of the performance to run a single-thread program on a dual-core processor,as well as a 75%waste on a 4-core processor.The multiple program logic can be run simultaneously by the multithread multicore processors,and the advantage of multicore processors can be given actually,which achieves the purpose of making full use of processors.To improve the performance of sorting operations,the flexible parallel library OpenMP and the quicksort function qsort provided in the C/C++language standard library are adopted.A parallel quicksort algorithm on any shared-memory parallel computer is implemented.The experimental results show that under the same condition,taking the standard library serial quicksort function qsort as the benchmark,the performance of the 200M random integer data has been increased by 11.92 times under the eight-thread condition on the Intel Core i7-4790 processor platform.On the same data,that of Intel Core 2 Quad Q9400 processor has been improved by 4.75 times.