Modified Bubble Sort
Let’s optimize the bubble sort.
We'll cover the following...
Introduction
The array is already sorted when there is no more swapping in one run of the outer loop. We stop sorting at this point. When we know that the array is almost sorted, the enhancement to the bubble sort can be particularly valuable.
Code example
Let’s optimize our code.
Press + to interact
package mainimport ("fmt")func ModifiedBubbleSort(arr []int, comp func(int, int) bool) {size := len(arr)swapped := 1for i := 0; i < (size-1) && swapped == 1; i++ {swapped = 0for j := 0; j < size-i-1; j++ {if comp(arr[j], arr[j+1]) {arr[j+1], arr[j] = arr[j], arr[j+1]swapped = 1 // check about swaping if its 0 mean already sorted.}}}}func more(value1 int, value2 int) bool {return value1 > value2}//Testing Codefunc main() {data := []int{9, 1, 8, 2, 7, 3, 6, 4, 5}ModifiedBubbleSort(data, more)fmt.Println(data)}
Complexity analysis
When an array is almost sorted, this innovation improves the best-case performance of this algorithm. We only need one pass in this scenario, and the best-case complexity is ...