We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Comparative Analysis of Comparison and Non Comparison based Sorting Algorithms

by Adolf Fenyi, Michael Fosu, Bright Appiah
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 175 - Number 28
Year of Publication: 2020
Authors: Adolf Fenyi, Michael Fosu, Bright Appiah
10.5120/ijca2020920813

Adolf Fenyi, Michael Fosu, Bright Appiah . Comparative Analysis of Comparison and Non Comparison based Sorting Algorithms. International Journal of Computer Applications. 175, 28 ( Oct 2020), 22-25. DOI=10.5120/ijca2020920813

@article{ 10.5120/ijca2020920813,
author = { Adolf Fenyi, Michael Fosu, Bright Appiah },
title = { Comparative Analysis of Comparison and Non Comparison based Sorting Algorithms },
journal = { International Journal of Computer Applications },
issue_date = { Oct 2020 },
volume = { 175 },
number = { 28 },
month = { Oct },
year = { 2020 },
issn = { 0975-8887 },
pages = { 22-25 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume175/number28/31628-2020920813/ },
doi = { 10.5120/ijca2020920813 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T00:39:43.761217+05:30
%A Adolf Fenyi
%A Michael Fosu
%A Bright Appiah
%T Comparative Analysis of Comparison and Non Comparison based Sorting Algorithms
%J International Journal of Computer Applications
%@ 0975-8887
%V 175
%N 28
%P 22-25
%D 2020
%I Foundation of Computer Science (FCS), NY, 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
Index Terms

Computer Science
Information Sciences

Keywords

Bubble Quick Merge Counting Radix and Time Complexity

Powered by PhDFocusTM