Home   >   CSC-OpenAccess Library   >    Manuscript Information
Full Text Available

(92.25KB)
This is an Open Access publication published under CSC-OpenAccess Policy.
Bidirectional Bubble Sort Approach to Improving the Performance of Introsort in the Worst Case for Large Input Size
Oyelami Olufemi Moses
Pages - 17 - 24     |    Revised - 01-10-2013     |    Published - 01-11-2013
Volume - 4   Issue - 2    |    Publication Date - November 2013  Table of Contents
MORE INFORMATION
KEYWORDS
Quicksort, Introsort, Bidirectional Bubble Sort, Worst Case, Improved Introsort
ABSTRACT
Quicksort has been described as the best practical choice for sorting. It is faster than many algorithms for sorting on most inputs and remarkably efficient on the average. However, it is not efficient in the worst case scenarios as it takes O(n2). Research efforts have been made to enhance this algorithm for the worst case scenarios by improving the way the algorithm chooses its pivot element for partitioning, but these approaches have the disadvantage of increasing the algorithm’s average computing time. Introsort was, however, developed to overcome this limitation. This paper presents an approach that uses Bidirectional Bubble Sort to improve the performance of Introsort. Instead of using Insertion Sort as the last step of the sorting algorithm for small lists, the approach uses Bidirectional Bubble Sort. The results of the implementation and experimentation of this algorithm compared with Introsort shows its better performance in the worst case scenario as the size of the list increases.
CITED BY (0)  
1 Google Scholar
2 CiteSeerX
3 refSeek
4 Scribd
5 SlideShare
6 PdfSR
1 S. Robert. Algorithms in C. USA: Addison-Wesley, 1998; pp. 1- 4, 267, 303.
2 A.W. Mark. Data Structures and Algorithm Analysis in C++. USA: Pearson Education.Inc., 2006, pp. 279.
3 H.C. Thomas, E.L. Charles, L.R. Ronald and S. Clifford. Introduction to Algorithm. USA:The Massachusetts Institute of Technology, 2001, pp. 25-26, 145.
4 A.D. Vladmir. Methods in Algorithmic Analysis. USA: CRC Press, 2010.
5 P.B. Shola. Data Structures With Implementation in C and Pascal. Nigeria: Reflect Publishers, 2003, pp. 134.
6 R.C. Singleton.(1969). “Algorithm 347 (An Efficient Algorithm for Sorting With Minimal Storage)”. Communications of the ACM, vol. 12, pp. 187-195, 1969.
7 M.O. Oyelami and I.O. Akinyemi. (2011, April). “Improving the Performance of Quicksort for Average Case Through a Modified Diminishing Increment Sorting.” Journal of Computing, 3(1), pp. 193-197. Available:http://www.scribd.com/doc/54847050/Improving-the-Performance-of-Quicksort-forAverage-Case-Through-a-Modified-Diminishing-Increment-Sorting
8 M. O. Oyelami (2008). “A Modified Diminishing Increment Sort for Overcoming the Search for Best Sequence of Increment for Shellsort.” Journal of Applied Sciences Research.[On-line], 4, pp. 760-766. Available: http://www.aensiweb.com/jasr/jasr/2008/760-766.pdf[Nov. 12, 2013]
9 M.O. Oyelami, A.A. Azeta and C.K Ayo. “Improved Shellsort for the Worst-Case, the Best-Case and a Subset of the Average-Case Scenarios.” Journal of Computer Science & Its Application. vol. 14, pp. 73 – 84, Dec. 2007.
10 D. Musser (1997). “Introspective Sorting and Selection Algorithms.” Software: Practice and Experience (Wiley). [On-line]. 27(8), pp. 983-993. Available: http://www-home.fhkonstanz.de/~bittel/prog2/Praktikum/musser97introspective.pdf[January 15, 2012].
11 “A guide to Introsort.” Internet: http://debugjung.tistory.com/entry/intro- sortintrospectivesort-????,[February 16, 2012].
12 E.K. Donald. The Art of Computer Programming. Volume 3, Sorting and Searching. USA:Addison-Wesley, 1998; pp. 110.
13 O.M. Oyelami. “Improving the performance of bubble sort using a modified diminishing increment sorting.” Scientific Research and Essay, vol. 4, pp. 740 -744, 2009.
14 S. Sartaj. Data Structures, Algorithms and Applications in Java. USA: McGrawHill, 2000,pp. 65 – 67.
15 F. William and T. William. Data Structures With C++ Using STL. USA: Prentice Hall,2002, pp. 131.
16 E.K. Donald. The Art of Computer Programming. Volume I, Fundamental Algorithms.USA: Addison-Wesley, 1997.
Dr. Oyelami Olufemi Moses
Covenant University, Ota, Ogun State, Nigeria - Nigeria
olufemioyelami@gmail.com