How To Do Bubble Sort in Go

Introduction

Bubble Sort is a simple sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they’re in the wrong order. While it’s not the most efficient sorting algorithm for large datasets, it’s easy to understand and implement, making it a great starting point for learning about sorting algorithms.

In this post, we’ll implement bubble sort in Go and explain how it works.

What is Bubble Sort?

Bubble Sort is a comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until no swaps are needed, indicating that the list is sorted.

Below, you can see a visualization of how Bubble Sort works. Choose the length of your array in the box next to Array Size (Max 30) then click Generate Random Array to generate the numbers, then click Start Sorting.

Time Complexity of Bubble Sort

• Best Case: O(n)—When the array is already sorted, Bubble Sort only needs to make one pass through it, making it O(n).
• Average Case: O(n²) – On average, the algorithm compares each element with each other, resulting in quadratic complexity.
• Worst Case: O(n²) – In the worst-case scenario, where the array is in reverse order, Bubble Sort has to make the maximum number of swaps, resulting in O(n²).

Space Complexity of Bubble Sort

• Space Complexity: O(1) – Bubble Sort is an in-place sorting algorithm requiring a constant amount of extra memory, regardless of the input size.

Pseudocode for Bubble Sort

The pseudocode for Bubble Sort outlines the basic steps of the algorithm:

procedure bubbleSort(arr)
    n = length(arr)
    repeat
        swapped = false
        for i = 0 to n-2 do
            if arr[i] > arr[i+1] then
                swap(arr[i], arr[i+1])
                swapped = true
        n = n - 1
    until swapped = false

Step-by-Step Explanation:

• You iterate through the array multiple times.
• During each pass, adjacent elements are compared, and if they are out of order, they are swapped.
• This process is repeated until no swaps occur during a complete pass, meaning the array is fully sorted.

Go Implementation of Bubble Sort

Here is how you can implement Bubble Sort in Go:

package main

import (
	"fmt"
)

// bubbleSort sorts a slice of integers in ascending order using the Bubble Sort algorithm
func bubbleSort(arr []int) {
	n := len(arr)
	if n < 2 {
		return // No need to sort if the slice has 0 or 1 element
	}

	for swapped := true; swapped; {
		swapped = false
		for i := 1; i < n; i++ {
			if arr[i-1] > arr[i] {
				// Swap adjacent elements
				arr[i-1], arr[i] = arr[i], arr[i-1]
				swapped = true
			}
		}
		n-- // Reduce the range of comparison after each pass
	}
}

func main() {
	arr := []int{64, 34, 25, 12, 22, 11, 90}
	fmt.Println("Unsorted array:", arr)

	bubbleSort(arr)

	fmt.Println("Sorted array:", arr)
}

Output

Unsorted array: [64 34 25 12 22 11 90]
Sorted array: [11 12 22 25 34 64 90]

Let’s break down the bubbleSort function:

1. We use two nested loops. The outer loop runs as long as swaps are being made, controlled by the swapped flag, and ensures multiple passes through the array until it is sorted.
2. In each iteration of the inner loop, we compare adjacent elements arr[i-1] and arr[i].
3. If arr[i-1] is greater than arr[i], we swap them. In Go, this can be done concisely in one line: arr[i-1], arr[i] = arr[i], arr[i-1].
4. The swapped flag tracks whether any swaps occurred during a pass. If no swaps happen, the slice is sorted, allowing the algorithm to exit early and optimise performance. Additionally, after each pass, the range of comparison is reduced by decrementing n, since the last elements are already in place.

Pros and Cons of Using Bubble Sort

Pros:

1. Simplicity: Bubble Sort is one of the most accessible algorithms to understand and implement, making it a good learning tool for beginners.
2. In-Place Sorting: It uses O(1) additional space, meaning it doesn’t require any extra data structures.
3. Stability: Bubble Sort is a stable sorting algorithm that preserves the relative order of elements with equal keys.

Cons:

1. Inefficiency: Its time complexity of O(n²) makes it inefficient for large datasets compared to more advanced algorithms like QuickSort or MergeSort.
2. Not Practical: Bubble Sort is rarely used in real-world applications where large data needs to be sorted due to its poor average-case performance.
3. Many Comparisons: Even if the array is nearly sorted, Bubble Sort makes unnecessary comparisons unless optimized further.

When to Use Bubble Sort

While Bubble Sort is not typically used in production-level applications due to its inefficiency, it can be useful in the following situations:

1. Small Datasets: Bubble Sort’s simplicity can make it a reasonable option for working with very small arrays.
2. Teaching and Learning: Bubble Sort is excellent for understanding the basic principles of sorting and how comparison-based algorithms work.
3. Stability Requirement: If you need a stable sorting algorithm and performance isn’t a concern, Bubble Sort can be used since it maintains the relative order of equal elements.
4. Pre-Sorted Data: In cases where the data is nearly or entirely sorted, Bubble Sort’s best-case performance of O(n) makes it a reasonable choice.

Conclusion

Bubble Sort is one of the simplest sorting algorithms for implementation and conceptual understanding. While it is inefficient for large datasets due to its O(n²) time complexity, it can still be useful in specific scenarios, such as small datasets or educational purposes. In Go, the algorithm’s implementation is straightforward and idiomatic, making it a great starting point for beginners learning both Go and sorting algorithms. However, you should consider using more efficient algorithms like Merge Sort or QuickSort for larger datasets. Understanding Bubble Sort is a foundational step toward grasping more complex sorting techniques, and its straightforward implementation in Go provides a great introduction to algorithmic thinking in the language.

Congratulations on reading to the end of this tutorial!

Read the following articles to learn how to implement Bubble Sort:

In Python – How to do Bubble Sort in Python

In C++ – How to Do Bubble Sort in C++

In Rust – How to do Bubble Sort in Rust

In JavaScript – How to do Bubble Sort in JavaScript

Have fun and happy researching!