Smart Bubble Sort: A Novel and Dynamic Variant of Bubble Sort Algorithm

In the present era, a very huge volume of data is being stored in online and offline databases. Enterprise houses, research, medical as well as healthcare organizations, and academic institutions store data in databases and their subsequent retrievals are performed for further processing. Finding the required data from a given database within the minimum possible time is one of the key factors in achieving the best possible performance of any computer-based application. If the data is already sorted, finding or searching is comparatively faster. In real-life scenarios, the data collected from different sources may not be in sorted order. Sorting algorithms are required to arrange the data in some order in the least possible time. In this paper, I propose an intelligent approach towards designing a smart variant of the bubble sort algorithm. I call it Smart Bubble sort that exhibits dynamic footprint: The capability of adapting itself from the average-case to the best-case scenario. It is an in-place sorting algorithm and its best-case time complexity is Ω(n). It is linear and better than bubble sort, selection sort, and merge sort. In average-case and worst-case analyses, the complexity estimates are based on its static footprint analyses. Its complexity in worst-case is O(n²) and in average-case is Θ(n²). Smart Bubble sort is capable of adapting itself to the best-case scenario from the average-case scenario at any subsequent stages due to its dynamic and intelligent nature. The Smart Bubble sort outperforms bubble sort, selection sort, and merge sort in the best-case scenario whereas it outperforms bubble sort in the average-case scenario.