A Heapify Based Parallel Sorting Algorithm
A Heapify Based Parallel Sorting Algorithm
复制标题
一种基于Heapify的并行排序算法
DOI：
10.3844/jcssp.2008.897.902
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Omer H. Abu Al haija
中科院分区：
文献类型：
--
作者：
Mwaffaq A. Abu Al hija;A. Zabian;S. Qawasmeh;Omer H. Abu Al haija
快速排序（英语：Quick sort）是一种排序算法，其最坏情况下的运行时间为θ（n2）。它是最实用的排序，因为它具有排序到位的优点。问题陈述：快速排序行为复杂，本文提出了原地2m线程并行堆排序算法，该算法在原地排序方面具有优势，在运行时间上优于经典的顺序快速排序。方法：该算法由几个阶段组成，第一阶段将输入数据分成两个分区，下一阶段对前一阶段进行相同的分区，直到达到2m个分区等于可用处理器的数量，最后使用堆排序对非内部排序的分区进行并行排序。结果：在输入量较大的情况下，该算法的速度约为经典快速排序算法的两倍。所需的比较次数大大减少。结论：在这项研究中，我们已经提出了一个排序算法，使用较少的比较相对于原始的快速排序，从而需要更少的运行时间来排序相同的输入数据。
Quick sort is a sorting algorithm whose worst case running time is θ(n2 ) on an input array of n numbers. It is the best practical for sorting because it has the advantage of sorting in place. Problem statement: Behavior of quick sort is complex, we proposed in-place 2m threads parallel heap sort algorithm which had advantage in sorting in place and had better performance than classical sequential quick sort in running time. Approach: The algorithm consisted of several stages, in first stage; it splits input data into two partitions, next stages it did the same partitioning for prior stage which had been spitted until 2 m partitions was reached equal to the number of available processors, finally it used heap sort to sort respectively ordered of non internally sorted partitions in parallel. Results: Results showed the speed of algorithm about double speed of classical Quick sort for a large input size. The number of comparisons needed was reduced significantly. Conclusion: In this study we had been proposed a sorting algorithm that uses less number of comparisons with respect to original quick sort that in turn requires less running time to sort the same input data.