Enhancement of Bubble and Insertion Sort Algorithm Using Block Partitioning
Tithi Paul · 2022
A list of components can be arranged in a certain order using a sorting algorithm, which is a fundamental concept in computer science. The temporal complexity of the two fundamental and widely used sorting algorithms, Bubble sort and Insertion sort is $\mathcal{O}\left( {{N^2}} \right)$, where N is the total number of items. When it comes to sorting a specific amount of items, it is superior. However, by adding more parts to its quadratic complexity, it loses efficiency. Because of this, it is less frequently employed in computer science’s practical and real-world applications, despite being widely utilized as a subroutine in other areas. Numerous extension techniques for the insertion sort and bubble sort algorithms have been put out in the literature, but none of them tries to combine the two to create a combination algorithm like ours. The bubble and insertion sort method was modified in this study, and its computational complexity was estimated to be $\mathcal{O}(N\sqrt N )$. The technique begins by dividing the input array into a few pieces, sorting each of the blocks using a modified bubble sort, and then merging all of the blocks together using a modified insertion sort. The suggested bubble and insertion sort outperform traditional bubble and insertion sorting as well as all other sorting algorithms with a computational complexity of $\mathcal{O}\left( {{N^2}} \right)$.