A Parallel Implementation of Dual-Pivot Quick Sort for Computers with Small Number of Processors
DOI:
https://doi.org/10.34818/INDOJC.2020.5.2.487Abstract
Sorting algorithms are heavily used. Quicksort is one of the fastest comparison-based sorting algorithms. These days almost all computing devices have multiple processors. There is a strong need of finding efficient parallel versions of the most common algorithms that are widely used. The basic version of quick sort is sequential and uses only one pivot. Recently, Yaroslavsky has proposed a modified version of the quick sort that uses two pivots and runs much faster than the single-pivot quick sort. Since then Java has incorporated this dual-pivot quick sort into its standard library for sorting. Although there are many parallel versions of the original single-pivot quick sort, there is a very few for the dual-pivot. Those few parallel versions of the dual-pivot quick sorts are compared with standard sort functions, rather than the dual-pivot quick sort itself. In this paper, we provide a parallel version of the dual-pivot quick sort algorithm of Yaroslavsky and implement it in Java. For comparison, we run both in small number of parallel processors. The experimental results show that our algorithm runs significantly faster than the Yaroslavsky’s algorithm. Moreover, our algorithm performs gradually better as the number of processors and the input size increase.Downloads
References
T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, 3rd ed. Cambridge, Massachusetts, USA, MIT Press, 2009.
D. E. Knuth, The Art of Computer Programming volume 3: Sorting and Searching, 2nd ed. Addison-Wesley. 1998.
P. Sanders, K. Mehlhorn, M. Dietzfelbinger, and R. Dementiev, Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox, Springer, 2019.
C. A. R. Hoare. (1962). Quicksort. Computer Journal. volume(5), pp. 10–16.
B. A. Cipra. (2000, May). The best of the 20th century: Editors name top 10 algorithms. SIAM News. volume(33), pp. 1-2.
R. Sedgewick. (1977). The analysis of quicksort programs, Acta Informatica. volume(7), pp. 327–355.
S. Wild and M. E. Nebel. (2012). Average case analysis of Java 7’s dual pivot quicksort. ESA, LNCS, Springer, Berlin. volume(7501), pp. 825–836.
J. Dongarra and F. Sullivan. (2000, January/February). Introduction: the top 10 algorithms, computing in science & engineering. IEEE. volume 2, pp. 22-23.
S. Taotiamton and S. Kittitornkun. (2017, November). A parallel dual-pivot quicksort algorithm with lomuto partition. 21st International Computer Science and Engineering Conference (ICSEC), Bangkok, Thailand, IEEE, pp. 15-18.
S. Taotiamton and S. Kittitornkun. (2017, June). Parallel hybrid dual pivot sorting algorithm. 14th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON), Phuket, Thailand, IEEE, pp. 27-30.
M. E. Nebel, S. Wild and C. MartÃnez. (2016). Analysis of pivot sampling in dual-pivot quicksort: a holistic analysis of Yaroslavskiy’s partitioning scheme. Algorithmica, Springer. volume (75), pp. 632-683.
S. Wild, M. E Nebel, and R. Neininger. (2015, January). Average case and distributional analysis of dual-pivot quicksort. ACM Transactions on Algorithms. volume (11), pp. 22.
S. Wild, M. E. Nebel and H. Mahmoud. (2016). Analysis of quickselect under Yaroslavskiy’s dual-pivoting algorithm. Algorithmica. volume (74), pp. 485–506.
S. Kushagra, A. López-Ortiz, J. I. Munro, and A. Qiao. (2014, January). Multi-pivot quicksort: theory and experiments. Proceedings of the Meeting on Algorithm Engineering & Expermiments (ALENEX), SIAM, pp. 47–60.
V. Yaroslavsky. (2009, September). Dual-Pivot Quicksort algorithm. Available: https://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf.
S. S. M. Al-Dabbagh and N. H. Barnouti. (2016, June). Parallel quicksort algorithm using OpenMP. International Journal of Computer Science and Mobile Computing. volume (5), pp.372–382.
P. Sanders and T. Hansch. (1997). Efficient massively parallel quicksort. International Symposium on Solving Irregularly Structured Problems in Parallel IRREGULAR 1997, Springer LNCS. volume (1253), pp. 13-24.
P. Tsigas and Y. Zhang. (2003, February). A simple, fast parallel implementation of quicksort and its performance evaluation on SUN Enterprise 10000. Eleventh Euromicro Conference on Parallel, Distributed and Network-Based Processing, Genova, Italy, IEEE, volume(5-7), pp. 372-381.
D. Cederman and P. Tsigas, (2010, January). GPU-Quicksort: a practical quicksort algorithm for graphics processors. Journal of Experimental Algorithmics, pp. 4.
D. Pasetto and A. Akhriev, (2011, October). A comparative study of parallel sort algorithms. proceedings of the ACM International Conference Companion on Object Oriented Programming Systems Languages and Applications, Portland, Oregon, USA, pp. 203-204.
B. A. Mahafzah. (2013). Performance assessment of multithreaded quicksort algorithm on simultaneous multithreaded architecture. Journal of Supercomputing, Springer. volume (66), pp. 339–363.
A. Rattanatranurak, (2018, June). Dual parallel partition sorting algorithm. Proceedings of 2018 the 8th International Workshop on Computer Science and Engineering (WCSE 2018), Bangkok, pp. 685 -690.
GeeksforGeeks. (2020). Serial Sort v/s Parallel Sort in Java. Available: https://www.geeksforgeeks.org/serial-sort-vs-parallel-sort-java/
Downloads
Published
How to Cite
Issue
Section
License
- Manuscript submitted to IndoJC has to be an original work of the author(s), contains no element of plagiarism, and has never been published or is not being considered for publication in other journals.Â
- Copyright on any article is retained by the author(s). Regarding copyright transfers please see below.
- Authors grant IndoJC a license to publish the article and identify itself as the original publisher.
- Authors grant IndoJC commercial rights to produce hardcopy volumes of the journal for sale to libraries and individuals.
- Authors grant any third party the right to use the article freely as long as its original authors and citation details are identified.
- The article and any associated published material is distributed under the Creative Commons Attribution 4.0License
