EXPLORE PUBLICATIONS BY COUNTRIES

Quicksort, Introsort, Bidirectional Bubble Sort, Worst Case, Improved Introsort

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.