Bidirectional Bubble Sort Approach to Improving the Performance of Introsort in the Worst Case for Large Input Size
No Thumbnail Available
Files
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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.
Keywords
QA75 Electronic computers. Computer science