Performance Analysis of Quicksort Algorithm: An Experimental Study of Its Variants

Authors

  • Amaal Shorman, Roqia Rateb, Areej Alshorman, Sawsan Abu Shqair

Keywords:

Experimental, Quicksort, Sorting, Algorithm Variants, Performance Evaluation.

Abstract

The Quicksort algorithm is often the best practice choice for sorting due to its remarkable efficiency on average cases, small constant factors hidden in the θ(n log n) notation, and its in-place sorting nature. This paper provides a comprehensive study and empirical results of the Quicksort algorithm and its variants. The study encompasses all Quicksort variants from 1961 to the present. Additionally, the paper compares the performance of different versions of Quicksort in terms of running time on integer arrays that are sorted, reversed, and randomly generated. Our work will be invaluable to anyone interested in studying and understanding the Quicksort algorithm and its various versions.

Downloads

Download data is not yet available.

References

Hoare, C., (1961). "Algorithm 64: Quicksort". Comm. ACM 4, 7 ,321.

Thoma, C., Charles, L., Ronald, L., and Clifford, S., (2009). "Introduction to Algorithms. Third Edition". The MIT Press. Cambridge, Massachusetts London, England.

Martnez, C., and Roura, S., (2002)."Optimal sampling strategies in Quicksort and Quickselect". SIAM Journal on Computing, 31(3).

Abdel, D., Thaer K, Azzam S., Manuel, S., Alfonso, O., (2012). "Enhancing QuickSort Algorithm using a Dynamic Pivot Selection Technique". Wulfenia Journal Klagenfurt, Austria. Vol 19, No. 10.

Sedgewick, R, (1978)." Implementing Quicksort programs". Communications of the ACM, 847 (2).

Loeser, R., (1976). "Survey on Algorithms 347, 426, and Quicksort". ACM Transactions on Mathematical Software (TOMS), Vol. 2 No. 3.

Mishra, A., and Garg, D., (2008). "Selection of Best Sorting Algorithm". International Journal of Intelligent Processing, 2(2), pp.363–368.

Ishwari, R., Bhawnesh, K., and Tinku, S.,(2012). Performance Comparison of Sequential Quick Sort and Parallel Quick Sort Algorithms. International Journal of Computer Applications, Vol.57, No.9, pp.14-22.

R.S. Scowen, (1965)."Algorithm 271: Quickersort", Comm. ACM 8,11, pp. 669-670.

R. C. Singleton, (1969). "Algorithm 347: An efficient algorithm for sorting with minimal storage", Comm. ACM 12, 3, pp. 186-187.

J. Bentley, (1984). "Programming Pearl: How to sort", Com.. ACM,Vol. 27 Issue 4.

B. McDaniel, (1991). "Variations on Put First", Conference on Applied Mathematics , University of Central Oklahoma.

R. L. Wainwright, (1985). "A class of sorting algorithms based on Quicksort", Comm. ACM, Vol. 28 Number 4.

R. L Wainright, (1987). "Quicksort algorithms with an early exit for sorted subfiles" ,Comm. ACM.

B. McDaniel, (1991). "Variations on Put First", Conference on Applied Mathematics , University of Central Oklahoma.

J. L. BENTLEY, M. D. McILROY, (1993). "Engineering a Sort Function". Software—Practice and Experience,Vol. 23(11), pp. 249 – 1265.

K.D. Neubert, (1997)."The FlashSort algorithm,” In Proc. of the euroFORTH'97 –Conf., Oxford, England, pp. 26 – 28,.

K. K. Sundararajan, and S. Chakraborty, (2006)." A new sorting algorithm", InterStat, Statistics on the Internet.

Sundararajan, KK, Pal, M, Chakarborty ,S., & Mahanti, NC, (2013) "K-Sort: A New Sorting Algorithm that beats Heap Sort for n ≤ 70 Lakhs!. Int. J. on Recent Trends in Engineering and Technology-IJRTET.

Aumüller, M., Dietzfelbinger, M., & Klaue, B. (2016). "Practical Quicksort variants with Yaroslavskiy’s dual-pivot algorithm". ACM Journal of Experimental Algorithmics, 21.

Edelkamp, S., & Weiss, A. (2022). "Recent Advances in Quicksort". ACM Computing Surveys, 54(7), Article 157.

Rahman, S., & Munro, J.I. (2023). "Enhanced Quicksort Techniques for Large Data Sets". Journal of Computer Science and Technology, 38(2), pp. 349-361.

Downloads

Published

12.06.2024

How to Cite

Amaal Shorman. (2024). Performance Analysis of Quicksort Algorithm: An Experimental Study of Its Variants. International Journal of Intelligent Systems and Applications in Engineering, 12(4), 4008 –. Retrieved from https://www.ijisae.org/index.php/IJISAE/article/view/6966

Issue

Vol. 12 No. 4 (2024)

Section

Research Article

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.

IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.