Go Program for Bubble Sort with Example and Explanation

A Go program for bubble sort uses nested for loops to repeatedly swap adjacent elements if they are in the wrong order, like for i := 0; i < n-1; i++ { for j := 0; j < n-i-1; j++ { if arr[j] > arr[j+1] { arr[j], arr[j+1] = arr[j+1], arr[j] } } }.

Examples

Input[5, 3, 8, 4, 2]

Output[2 3 4 5 8]

Input[1, 2, 3, 4, 5]

Output[1 2 3 4 5]

Input[9]

Output[9]

How to Think About It

To sort a list using bubble sort, compare each pair of adjacent items and swap them if they are in the wrong order. Repeat this process until no swaps are needed, which means the list is sorted.

Algorithm

1

Get the list of numbers to sort.

2

Start from the beginning of the list and compare each pair of adjacent elements.

3

If the first element is greater than the second, swap them.

4

Repeat the process for the entire list, reducing the range each time because the largest elements settle at the end.

5

Continue until no swaps are made in a full pass, indicating the list is sorted.

6

Return the sorted list.

Code

go

package main

import "fmt"

func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

func main() {
    arr := []int{5, 3, 8, 4, 2}
    bubbleSort(arr)
    fmt.Println(arr)
}

Output

[2 3 4 5 8]

Dry Run

Let's trace the array [5, 3, 8, 4, 2] through the bubble sort code.

1

First pass comparisons and swaps

Compare 5 and 3, swap -> [3, 5, 8, 4, 2]; compare 5 and 8, no swap; compare 8 and 4, swap -> [3, 5, 4, 8, 2]; compare 8 and 2, swap -> [3, 5, 4, 2, 8]

2

Second pass comparisons and swaps

Compare 3 and 5, no swap; compare 5 and 4, swap -> [3, 4, 5, 2, 8]; compare 5 and 2, swap -> [3, 4, 2, 5, 8]

3

Third pass comparisons and swaps

Compare 3 and 4, no swap; compare 4 and 2, swap -> [3, 2, 4, 5, 8]

4

Fourth pass comparisons and swaps

Compare 3 and 2, swap -> [2, 3, 4, 5, 8]

Pass	Array State After Pass
1	[3 5 4 2 8]
2	[3 4 2 5 8]
3	[3 2 4 5 8]
4	[2 3 4 5 8]

Why This Works

Step 1: Compare adjacent elements

The code uses if arr[j] > arr[j+1] to check if two neighbors are out of order.

Step 2: Swap if needed

If the left element is bigger, it swaps places with the right one using arr[j], arr[j+1] = arr[j+1], arr[j].

Step 3: Repeat passes

The outer loop repeats the process, shrinking the range each time because the largest elements settle at the end.

Alternative Approaches

Optimized Bubble Sort with Early Exit

go

package main

import "fmt"

func bubbleSortOptimized(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        swapped := false
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = true
            }
        }
        if !swapped {
            break
        }
    }
}

func main() {
    arr := []int{5, 3, 8, 4, 2}
    bubbleSortOptimized(arr)
    fmt.Println(arr)
}

Stops early if no swaps happen in a pass, improving performance on nearly sorted lists.

Using Go's sort Package

go

package main

import (
    "fmt"
    "sort"
)

func main() {
    arr := []int{5, 3, 8, 4, 2}
    sort.Ints(arr)
    fmt.Println(arr)
}

Uses Go's built-in efficient sort, which is faster and simpler but does not show bubble sort logic.

Complexity: O(n^2) time, O(1) space

Time Complexity

Bubble sort uses nested loops, each running up to n times, resulting in O(n^2) time in the worst and average cases.

Space Complexity

It sorts the array in place, so it uses only O(1) extra space.

Which Approach is Fastest?

Using Go's built-in sort is fastest for real use, while optimized bubble sort can be faster than basic bubble sort on nearly sorted data.

Approach	Time	Space	Best For
Basic Bubble Sort	O(n^2)	O(1)	Learning and small datasets
Optimized Bubble Sort	O(n) best, O(n^2) worst	O(1)	Nearly sorted data
Go's sort.Ints	O(n log n)	O(log n)	All practical sorting needs