Abstract

In everyday life there is a large amount of data to arrange because sorting removes any ambiguities and make the data analysis and data processing very easy, efficient and provides with cost less effort. In this study a set of improved sorting algorithms are proposed which gives better performance and design idea. In this study five new sorting algorithms (Bi-directional Selection Sort, Bi-directional bubble sort, MIDBiDirectional Selection Sort, MIDBidirectional bubble sort and linear insertion sort are presented. Bi-directional Selection Sort and MIDBiDirectional Selection Sort are the enhancement on basic selection sort while Bidirectional bubble sort and MIDBidirectional bubble sort are the enhancement on basic bubble sort by changing the selection and swapping mechanism of data for sorting. Enhanced sorting algorithms reduced the iteration by half and quarter times respectively. Asymptotically complexities of these algorithms are reduced to O (n2/2) and O (n2/4) from O (n2). Linear insertion sort is the enhancement of insertion sort by changing the design of algorithm (convert two loops to one loop). So asymptotically this algorithm is converted to linear time complexity from quadratic complexity. These sorting algorithms are described using C. The proposed algorithms are analyzed using asymptotic analysis and also using machine-running time and compared with their basic sorting algorithms. In this study we also discuss how the performance and complexity can be improved by optimizing the code and design.

Keywords:

2-element insertion sort, 2-way bubble sort, 2-way mid bubble sort, 2-way mid selection sort, 2-way selection sort, asymptotic analysis, bubble sort, insertion sort , running time, selection sort,

References

1. Astrachan, O., 2003. Bubble sort: An archaeological algorithmic analysis. Proceeding of the 34th SIGCSE Technical Symposium on Computer Science Education (SIGCSE '03), 35(1): 1-5.
   CrossRef    
2. Cormen, T., C. Leiserson, R. Rivest and C. Stein, 2004. Introduction to Algorithms. 1st Edn., McGraw Hill, USA.
   
3. Deitel, H.M. and P.J. Deitel, 1998. C++ How to Program. 1st Edn., Prentice Hall, Upper Saddle River, NJ.
   
4. Friend, E., 1956. Sorting on electronic computer systems. J. ACM (JACM), 3(3): 134-168.
   CrossRef    
5. Hoare, C., 1962. Quick sort. Comput. J., 5(1): 10-16.
   CrossRef    
6. Khamitkar, S., P. Bhalchra, S. Lokhe and N. Deshmukh, 2010. The folklore of sorting algorithms. Int. J. Comput. Sci. Issues, 7(4).
   
7. Mansi, R., 2010. A new algorithm for sorting small integers. Int. Arab J. Inf. Techn., 7(2).
   
8. Min, W., 2010. Analysis on bubble sort algorithm optimization. Proceeding of International Forum on Information Technology and Applications (IFITA, 2010), 1: 208-211.
   CrossRef    
9. Shell, D., 1959. A high-speed sorting procedure. Commun. ACM, 2(7): 30-32.
   CrossRef    
10. Vitányi, P., 2007. Analysis of Sorting Algorithms by Kolmogorov Complexity (a Survey). In: Csiszár, I., G.O.H. Katona and G. Tard ´os (Eds.), Entropy Search Complexity. Number 16 in Bolyai Society Mathematical Studies, pp: 209-232.
    
11. Weimin, Y. and W. Weimin, 2000. Data Structures. 1st Edn., Tsinghua Universit Press, Beijing, pp: 263-268.
    
12. Xiaokai, X., 1995. Simple Data Structure Tutorial. 1st Edn., Tsinghua University Press, Beijing, pp: l93-196.
    
13. Xusong, X., 1996. Introduction to Data Structures and Algorithms. 1st Edn., Electronics Industry Press, Beijing, pp: 162-164.
    

Competing interests

The authors have no competing interests.

Open Access Policy

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Copyright

The authors have no competing interests.