Bubble Sort in Go

👋 Welcome Gophers! In this video, we are going to be covering how we can implement the bubble sorting algorithm that we looked at in the last video.

Implementation

Let’s start off by creating a new file called main.go within a new directory called 01-bubble-sort/. I’ll be segregating each sorting and searching algorithm into a separate named directory under the one repository just for ease.

Let’s start by creating a simple main function that prints out something.

package main

import "fmt"

func main() {
  fmt.Println("Bubble Sorting Algorithm in Go")
}

Now, let’s start off by defining the function signature for our bubble sort function.

// BubbleSort - takes in a slice of ints and returns a sorted slice of ints
func BubbleSort(input []int) []int {

}

We want this function to take in a slice of integers and then return another slice which has been sorted.

Now, let’s take a stab at filling out this new BubbleSort function. We want to start by defining n which will be equal to the length of our slice of ints. We also want to declare a new swapped bool and initialize this to true:

func BubbleSort(input []int) []int {
  n := len(input)
  swapped := true
}

Next, we want to create a for loop that is going to contain the logic for comparing each element in the array:

for swapped {
  // set swapped to false
  swapped = false
  // iterate through all of the elements in our list
  for i := 0; i < n-1; i++ {
    // if the current element is greater than the next
    // element, swap them
    if input[i] > input[i+1] {
      // log that we are swapping values for posterity
      fmt.Println("Swapping")
      // swap values using Go's tuple assignment
      input[i], input[i+1] = input[i+1], input[i]
      // set swapped to true - this is important
      // if the loop ends and swapped is still equal
      // to false, our algorithm will assume the list is
      // fully sorted.
      swapped = true
    }
  }
}

Awesome, at this point, we should have a fully functional implementation of our Bubble Sort algorithm! Let’s test it out by creating a slice within our main function and then calling our new BubbleSort function:

func main() {
  fmt.Println("Bubble Sorting Algorithm in Go")

  unsortedInput := []int{5,3,4,1,2}
  sorted := BubbleSort(unsortedInput)

  fmt.Println(sorted)
}

Perfect, let’s give this a shot and try and run it from the command line:

$ go run main.go
Bubble Sorting Algorithm in Go
Swapping
Swapping
Swapping
Swapping
Swapping
Swapping
Swapping
Swapping
[1 2 3 4 5]

Perfect, we now have a sorted slice of ints and we’ve also got the number of times a swap has been performed through counting the number of times Swapping has been printed out.

Conclusion

Awesome, we now have a working implementation of the bubble sorting algorithm written in Go!

Quiz Time

Try your hand at these questions below to validate what we’ve just covered in this lesson: