An Enhanced Bubble Sorting Algorithm with Divide and Conquer Approach Leads to the Construction of Balanced Search Tree

Abstract

Tree is a best data structure for data storage and retrieval of data whenever it could be accommodated in the memory. At the same time, this is true only when the tree is height-balanced and lesser depth from the root. In this paper, we propose a new sorting algorithm, which is the enhancement of the bubble sort. This new sorting algorithm with divide and conquer approach leads to construct the Binary Search Tree. To maintain the tree in shape and depth, we apply two strategies in the input data. The first one is to apply new sorting technique on the given input data. And the second one is to recursively apply divide and conquer approach on the sorted input data. After, a new input data is formed. Then construct the Binary search tree on the given input data as output. At last, we will find the output as; a height balanced BST (AVL) with lesser depth from the root, and the search cost is minimum as possible. In this paper, few case studies have been carried out and analyzed in terms of height and space requirement, and the iterations required to sort out the data with other sorting methods. Hence, the height of the output BST, normally obtain by maximum height as N/2 or (N/2) – 3. And comparatively with Bubble sort which needs only less number of iterations. And the new enhancement Bubble sorting algorithm is performing minimum of 43 % increases with Bubble sort performance.