Search⌘ K
AI Features
Home
Courses
Data Structures & Algorithms In Go

Modified Bubble Sort

Explore how to implement the modified bubble sort algorithm in Go for improved efficiency when arrays are nearly sorted. Understand the stopping condition that detects sorted data, study code optimization, and analyze performance complexities including best-case and worst-case scenarios. This lesson helps you recognize adaptive sorting benefits and develop stable sorting techniques in Go.

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.

Go (1.6.2)
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) ...