Home   >   CSC-OpenAccess Library   >    Manuscript Information
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.
1 Google Scholar 
2 CiteSeerX 
3 refSeek 
4 Scribd 
5 SlideShare 
6 PdfSR 
A.D. Vladmir. Methods in Algorithmic Analysis. USA: CRC Press, 2010.
A.W. Mark. Data Structures and Algorithm Analysis in C++. USA: Pearson Education.Inc., 2006, pp. 279.
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].
E.K. Donald. The Art of Computer Programming. Volume 3, Sorting and Searching. USA:Addison-Wesley, 1998; pp. 110.
E.K. Donald. The Art of Computer Programming. Volume I, Fundamental Algorithms.USA: Addison-Wesley, 1997.
F. William and T. William. Data Structures With C++ Using STL. USA: Prentice Hall,2002, pp. 131.
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.
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]
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
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.
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.
P.B. Shola. Data Structures With Implementation in C and Pascal. Nigeria: Reflect Publishers, 2003, pp. 134.
R.C. Singleton.(1969). “Algorithm 347 (An Efficient Algorithm for Sorting With Minimal Storage)”. Communications of the ACM, vol. 12, pp. 187-195, 1969.
S. Robert. Algorithms in C. USA: Addison-Wesley, 1998; pp. 1- 4, 267, 303.
S. Sartaj. Data Structures, Algorithms and Applications in Java. USA: McGrawHill, 2000,pp. 65 – 67.
“A guide to Introsort.” Internet: http://debugjung.tistory.com/entry/intro- sortintrospectivesort-????,[February 16, 2012].
Dr. Oyelami Olufemi Moses
Covenant University, Ota, Ogun State, Nigeria - Nigeria
olufemioyelami@gmail.com