Data Structures & Algorithms In Go/

...

/

Bubble Sort

Bubble Sort

Let’s learn about the bubble sort in detail.

We'll cover the following...

Introduction

Bubble sort is the slowest sorting algorithm. However, when the data is small, it is simple to implement and use.

How bubble sort works

In bubble sort, we compare each pair of adjacent values. We want to sort values in increasing order, so if the second value is less than the first value, we swap these two values. Otherwise, we go to the next pair. This way, the largest values bubble to the end of the array.

The greatest value will be at the rightmost position after the first pass. We’ll go over the array n times to completely sort it. Let’s look at an illustration of the first pass of bubble sort on an unsorted list.

Code example

Press + to interact
package main
import ("fmt")
func BubbleSort(arr []int, comp func(int, int) bool) { 
  size := len(arr)
    for i := 0; i < (size - 1); i++ {
        for j := 0; j < size-i-1; j++ {
            if comp(arr[j], arr[j+1]) {
                /* Swapping */
                arr[j+1], arr[j] = arr[j], arr[j+1]
            }
        } 
      }
}
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} 
  BubbleSort(data, more)
  fmt.Println(data)
}

Analysis

  • The number of swaps performed for data comparison is shown by the outer loop.

  • The data comparison is made in the inner loop. The largest value is relocated to the end of the array at the end of each internal loop iteration. Thus, at the end of the first iteration, the largest value will be at the end of the array, at the end of the ...