...

/

Modified Bubble Sort

Modified Bubble Sort

Let’s optimize the bubble sort.

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 main
import ("fmt")
func ModifiedBubbleSort(arr []int, comp func(int, int) bool) {
size := len(arr)
swapped := 1
for i := 0; i < (size-1) && swapped == 1; i++ {
swapped = 0
for 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 Code
func 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 O(n)O(n) ...