Call for Paper - September 2022 Edition
IJCA solicits original research papers for the September 2022 Edition. Last date of manuscript submission is August 22, 2022. Read More

Comparative Analysis of Comparison and Non Comparison based Sorting Algorithms

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2020
Authors:
Adolf Fenyi, Michael Fosu, Bright Appiah
10.5120/ijca2020920813

Adolf Fenyi, Michael Fosu and Bright Appiah. Comparative Analysis of Comparison and Non Comparison based Sorting Algorithms. International Journal of Computer Applications 175(28):22-25, October 2020. BibTeX

@article{10.5120/ijca2020920813,
	author = {Adolf Fenyi and Michael Fosu and Bright Appiah},
	title = {Comparative Analysis of Comparison and Non Comparison based Sorting Algorithms},
	journal = {International Journal of Computer Applications},
	issue_date = {October 2020},
	volume = {175},
	number = {28},
	month = {Oct},
	year = {2020},
	issn = {0975-8887},
	pages = {22-25},
	numpages = {4},
	url = {http://www.ijcaonline.org/archives/volume175/number28/31628-2020920813},
	doi = {10.5120/ijca2020920813},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

Abstract

Sorting is one of the most important task in many computer applications. Efficiency becomes a big problem when the sorting involves a large amounts of data. There are a lot of sorting algorithms with different implementations. Some of them sort data by comparison while others don’t. The main aim of this thesis is to evaluate the comparison and non-comparison based algorithms in terms of execution time and memory consumption. Five main algorithms were selected for evaluation. Out of these five, three were comparison based algorithms (quick, bubble and merge) while the remaining two were non-comparison based (radix and counting). After conducting an experiment using array of different data sizes (ranging from 1000 to 35000), it was realized that the comparison based algorithms were less efficient than the non-comparison ones. Among the comparison algorithms, bubble sort had the highest time complexity due to the swapping nature of the algorithm. It never stops execution until the largest element is bubbled to the right of the array in every iteration. Despite this disadvantage, it was realized that it is memory efficient since it does not create new memory in every iteration. It relies on a single memory for the swapping array operation. The quick sort algorithm uses a reasonable amount of time to execute, but has a poor memory utilization due to the creation of numerous sub arrays to complete the sorting process. Among the comparison based algorithms, merge sort was far better than both quick and bubble. On the average, merge sort utilized 32.261 seconds to sort all the arrays used in the experiment while quick and bubble utilized 41.05 and 165.11 seconds respectively. The merge algorithm recorded an average memory consumption of 5.5MB for all the experiment while quick and bubble recorded 650.792MB and 4.54MB respectively. Even though the merge sort is better than both quick and bubble, it cannot be compared to the non-comparison based algorithms since they perform far better than the comparison based ones. When the two groups were evaluated against execution time, the comparison based algorithms recorded an average score of 476.757 seconds while the non-comparison obtained 17.849 seconds. With respect to the memory utilization, the non-comparison based algorithms obtained 27.12MB while the comparison ones obtained 1321.681MB. This clearly reveals the efficiency of the non-comparison based algorithms over the comparison ones in terms of execution time and memory utilization.

References

  1. M.S. Garai Canaan.C and M. Daya. Popular sorting algorithms. World Applied Programming, 1:62{71, April 2011.
  2. A.D. Mishra and D. Garg. Selection of Best Sorting Algorithm. International Journal of Intelligent Processing, 2(2):363{368, July-December 2008.
  3. Pankaj Sareen. Comparison of sorting Algorithms (on the basis of average case). IJARCSSE, 3:522{532, March 2013.
  4. Donald E.Knuth. The Art of Computer Programming Second Edition, volume 3. ADDISON-WESLEY, 1998.
  5. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 2009.
  6. Omar khan Durrani, Shreelakshmi V, Sushma Shetty, and Vinutha D C. Analysis and determination of asymptotic behavior range for popular sorting algorithms. Special Issue of International Journal of Computer Science Informatics (IJCSI), ISSN(PRINT):2231-5292, Vol-2, Issue-1,2.
  7. Coenrad Bron. Merge sort algorithm [m1] (algorithm 426). Commununication , ACM, 15(5):357, 1972.
  8. Harold H Seward. Information sorting in the application of electronic digital computers to business operations. Master’s thesis, M.I.T, 1954.
  9. Clifford A. Shaffer. A Practical Introduction to Data Structures and Algorithm Analysis Third Edition. Prentice Hall, April 2009.
  10. D. L. Shell. A high-speed sorting procedure. Commun. ACM, 2(7):30{32, July 1959.
  11. B.L Teague, The Quick sort implementation in PHP, accessed 13th January 2020, https://medium.com/the-protean-journal/the-quicksort-algorithm-implemented-in-php
  12. J. M Shaffer, Bubble Sort Algorithm in PHP, accessed 20th July 2020, https://eresdev.com/bubble-sort-algorithm-in-php
  13. Codexpedia, Merge sort Implementation in PHP, accessed 7th June 2020, https://www.codexpedia.com/php/merge-sort-example-in-php/
  14. K.T Toida, PHP Program - Radix Sort, accessed 15th June 2020, https://www.alphacodingskills.com/php/pages/php-program-for-radix-sort.php.
  15. I. Wegener, PHP Program - Counting Sort, accessed 10th May 2020, https://www.alphacodingskills.com/php/pages/php-program-for-counting-sort.php

Keywords

Bubble, Quick, Merge, Counting, Radix and Time Complexity