Research Article | OPEN ACCESS
Enhancement of Selection, Bubble and Insertion Sorting Algorithm
Muhammad Farooq Umar, Ehsan Ullah Munir, Shafqat Ali Shad and Muhammad Wasif Nisar
Department of Computer Science, COMSATS Institute of Information Technology, Wah Cantt, Pakistan
Research Journal of Applied Sciences, Engineering and Technology 2014 2:263-271
Received: April 15, 2014 | Accepted: May 25, 2014 | Published: July 10, 2014
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
-
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 -
Cormen, T., C. Leiserson, R. Rivest and C. Stein, 2004. Introduction to Algorithms. 1st Edn., McGraw Hill, USA.
-
Deitel, H.M. and P.J. Deitel, 1998. C++ How to Program. 1st Edn., Prentice Hall, Upper Saddle River, NJ.
-
Friend, E., 1956. Sorting on electronic computer systems. J. ACM (JACM), 3(3): 134-168.
CrossRef -
Hoare, C., 1962. Quick sort. Comput. J., 5(1): 10-16.
CrossRef -
Khamitkar, S., P. Bhalchra, S. Lokhe and N. Deshmukh, 2010. The folklore of sorting algorithms. Int. J. Comput. Sci. Issues, 7(4).
-
Mansi, R., 2010. A new algorithm for sorting small integers. Int. Arab J. Inf. Techn., 7(2).
-
Min, W., 2010. Analysis on bubble sort algorithm optimization. Proceeding of International Forum on Information Technology and Applications (IFITA, 2010), 1: 208-211.
CrossRef -
Shell, D., 1959. A high-speed sorting procedure. Commun. ACM, 2(7): 30-32.
CrossRef -
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.
-
Weimin, Y. and W. Weimin, 2000. Data Structures. 1st Edn., Tsinghua Universit Press, Beijing, pp: 263-268.
-
Xiaokai, X., 1995. Simple Data Structure Tutorial. 1st Edn., Tsinghua University Press, Beijing, pp: l93-196.
-
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.
|
|
![](http://www.maxwellsci.com/images/RJASET-maxw.jpg) |
ISSN (Online): 2040-7467
ISSN (Print): 2040-7459 |
![Submit Manuscript](../images/sub.jpg) |
Information |
|
|
|
Sales & Services |
|
|
|