Look Back Sort : A Backward Comparison Algorithm for Internal Sorting

Authors

  • Jyoti Lakhani  Department of Computer Science, Maharaja Ganga Singh University, Bikaner, Rajasthan, India
  • Kirti Shrimali  Department of Computer Science, Maharaja Ganga Singh University, Bikaner, Rajasthan, India
  • Dharmesh Harwani  Department of Microbiology, Maharaja Ganga Singh University, Bikaner, Rajasthan, India

Keywords:

internal sorting, backward comparison, benchmarking, empirical study, space complexity, time complexity

Abstract

Present communication is an attempt to develop a novel algorithm "Look-Back Sort" (LB Sort) for internal sorting. The objective of the present research work was to reduce the space and time complexities of the sorting process in the worst cases. The performance of all internal sorting algorithms in worst cases are bound to O(n log n). To address the issue, the proposed algorithm is implemented first followed by its benchmarking with some other internal sorting algorithms. The empirical analysis of algorithms using C++ function is performed on the numeric samples vary in size. It was observed that the runtime of the LB-sort algorithm is highly comparable with the Quick sort algorithm in the worst case analysis. The overall time complexity of the proposed algorithm is observed to be O(n log k) when k<

References

  1. https://en.wikipedia.org/wiki/Sorting_algorithm downloaded on December 20, 2017
  2. T.H. Cormen, C.E. Leiserson, R.L. Rivest. C. Stein, 2001. “Introduction to Algorithms”, 2nd edition, MIT press,
  3. A.M. Aliyu and Dr. P.B. Zirra, 2013. “A Comparative Analysis of Sorting Algorithms on Integer and. Character Arrays”, The International Journal Of Engineering And Science (IJES), vol. 2, no. 7, (2013), pp. 25-30.
  4. I. Flores. 1960. “Analysis of Internal Computer Sorting”, ACM, vol. 7, no. 4, (1960), pp. 389- 409.
  5. C.A.R. Hoare. 1961. Algorithm 64: Quick sort. Comm. ACM, vol. 4, no. 7 (1961), pp. 321.
  6. Selection Sort,  http://www.algolist.net/Algorithms/ Sorting/Selection_sort
  7. E. Horowitz, S. Sahni and S. Rajasekaran, first edition, 1987. “Computer Algorithms”,Computer Science Press, New York.
  8. S. Lipschutz, 1986. “Theory and Problems of Data Structure”, McGraw Hill Book Company.
  9. Md. Khairullah, 2013. International Journal of Advanced Science and Technology Vol. 56, July, 2013.
  10. Sengupta et al., 2007. “Algorithms in Java”, 3rd ed., Part 1-4, Addison-Wesley Professional Publisher, New York.
  11. J. Hammad, 2015. “A Comparative Study between Various Sorting Algorithms”, International Journal of Computer Science and Network Security, VOL.15 No.3.
  12. Jr P.W., C.A. Brown. 1985. “The analysis of algorithms”. Holt, Rinehart & Winston, New York.
  13. S. Baase. 1988. “Computer algorithms: Introduction to analysis and design”, Addison Wesley, Reading, Massachusetts,1988.
  14. R. E. Neapolitan, K. Naimipour. 2010. “Foundations of algorithms”, Jones & Bartlett Learning.
  15. U. Manber. 1989.  “Introduction to algorithms: A creative approach”, Addison-Wesley Longman Publishing Co., Inc.

IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology

Downloads

Published

2017-12-31

Issue

Volume 2, Issue 6, November-December-2017

Section

Research Articles

License

Copyright (c) IJSRCSEIT

Creative Commons License

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

How to Cite

[1]
Jyoti Lakhani, Kirti Shrimali, Dharmesh Harwani, " Look Back Sort : A Backward Comparison Algorithm for Internal Sorting, IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology(IJSRCSEIT), ISSN : 2456-3307, Volume 2, Issue 6, pp.1239-1243, November-December-2017.