Implementing Bubble Sort Algorithm in Go

What is a Bubble Sort?

Bubble sort is a simple sorting algorithm that is used to sort a given set of n elements usually provided in form of an array. Bubble sorting compares all the elements one by one and sorts them based on their values. If the given array has to be sorted in ascending order, then bubble sort will start by comparing the first element of the array with the second element, if the first element is greater than the second element, it will swap both the elements and then move on to compare the second and the third element, and so on. If we have total n elements, then we need to repeat this process for n-1 times.

It is known as bubble sort because with every complete iteration the largest element in the given array bubbles up towards the last place or the highest index, just like a water bubble rises to the water surface.

With a worst-case complexity of O(n^2), bubble sort is very slow compared to other sorting algorithms but it is also a very easy sorting algorithm to understand.

How to implement the bubble sort algorithm

In ascending order:

Starting with the first element in the array, compare the current element with the next element in the array.
If the current element is greater than the next element in the array, swap them.
If the current element is less than the next element, move to the next element.
Repeat.

Writing the code in Go

Do read the comments in the code below to understand the process

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

    for swapped {
        // set swapped to false
        swapped = false
        // iterate through all of the elements in our array(splice)
        for i := 0; i < length-1; i++ {
            // if the current element is greater than the next
            // element, swap them
            if input[i] > input[i+1] {
                // swap values using Go's tuple assignment
                input[i], input[i+1] = input[i+1], input[i]
                // set swapped to true - this is important
                // because if the loop ends
                // and swapped is still equal
                // to false, our algorithm will assume
                // the list is fully sorted.
                swapped = true
            }
        }
    }
    return input
}

We can now test our function in the command line by

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

  unsortedInput := []int{9, 5, 7, 3, 8, 4, 1, 10, 6, 2}
  sorted := BubbleSort(unsortedInput)

  fmt.Println(sorted)
}

Complexity analysis of bubble sort

Worst Case Time Complexity [ Big-O ]: O(n2)
Best Case Time Complexity [Big-omega]: O(n)
Average Time Complexity [Big-theta]: O(n2)
Space Complexity: O(1)

Clearly, bubble sort is not the most efficient sorting algorithm. Follow this blog to read my upcoming articles on much more efficient algorithms.

I hope this was worth your time, do leave comments or suggestions as this is my first article, and thanks for reading!

Daniel Etuk