Bubble Sort Algorithm in DSA Go

Mental Model

Bubble sort repeatedly swaps adjacent items if they are in the wrong order, pushing the largest unsorted item to the end each pass.

Analogy: Imagine bubbles rising in water: the biggest bubble slowly moves up to the surface by swapping places with smaller bubbles below it.

Index: 0   1   2   3   4
Array: [5]->[3]->[8]->[4]->[2]

Dry Run Walkthrough

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

Goal: Sort the array in ascending order using bubble sort

Step 1: Compare 5 and 3, swap because 5 > 3

[3] -> [5] -> [8] -> [4] -> [2]

Why: Smaller number should come before larger, so swap to start sorting

Step 2: Compare 5 and 8, no swap because 5 < 8

[3] -> [5] -> [8] -> [4] -> [2]

Why: Order is correct, no need to swap

Step 3: Compare 8 and 4, swap because 8 > 4

[3] -> [5] -> [4] -> [8] -> [2]

Why: 8 is bigger, so it moves towards the end

Step 4: Compare 8 and 2, swap because 8 > 2

[3] -> [5] -> [4] -> [2] -> [8]

Why: 8 bubbles up to the last position

Step 5: Start second pass: Compare 3 and 5, no swap

[3] -> [5] -> [4] -> [2] -> [8]

Why: 3 < 5, order is correct

Step 6: Compare 5 and 4, swap because 5 > 4

[3] -> [4] -> [5] -> [2] -> [8]

Why: 5 moves towards the end

Step 7: Compare 5 and 2, swap because 5 > 2

[3] -> [4] -> [2] -> [5] -> [8]

Why: 5 moves closer to its correct position

Step 8: Start third pass: Compare 3 and 4, no swap

[3] -> [4] -> [2] -> [5] -> [8]

Why: 3 < 4, order is correct

Step 9: Compare 4 and 2, swap because 4 > 2

[3] -> [2] -> [4] -> [5] -> [8]

Why: 4 moves towards the end

Step 10: Start fourth pass: Compare 3 and 2, swap because 3 > 2

[2] -> [3] -> [4] -> [5] -> [8]

Why: 2 moves to the front, array is sorted now

Result:

[2] -> [3] -> [4] -> [5] -> [8]

Annotated Code

DSA Go

package main

import "fmt"

func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        swapped := false
        for j := 0; j < n-1-i; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j] // swap adjacent elements
                swapped = true
            }
        }
        if !swapped {
            break // stop if no swaps in this pass
        }
    }
}

func main() {
    arr := []int{5, 3, 8, 4, 2}
    bubbleSort(arr)
    for i, v := range arr {
        if i > 0 {
            fmt.Print(" -> ")
        }
        fmt.Print(v)
    }
    fmt.Println()
}

for i := 0; i < n-1; i++ {

outer loop controls passes over the array

swapped := false

track if any swaps happen this pass

for j := 0; j < n-1-i; j++ {

inner loop compares adjacent pairs up to last sorted element

if arr[j] > arr[j+1] {

compare adjacent elements to decide if swap needed

arr[j], arr[j+1] = arr[j+1], arr[j]

swap elements to bubble larger one up

swapped = true

mark that a swap occurred this pass

if !swapped { break }

stop early if no swaps, array is sorted

Output

2 -> 3 -> 4 -> 5 -> 8

Complexity Analysis

Time: O(n^2) because in worst case we compare and swap pairs for each element multiple times

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Compared to more advanced sorts like quicksort (O(n log n)), bubble sort is slower but simpler to understand and implement

Edge Cases

empty array

function returns immediately without error

DSA Go

for i := 0; i < n-1; i++ {

array with one element

no swaps needed, array remains same

DSA Go

for i := 0; i < n-1; i++ {

already sorted array

early break after first pass because no swaps occur

DSA Go

if !swapped { break }

When to Use This Pattern

When you see a problem asking to sort a small list with simple swaps and no extra space, bubble sort is a good first approach because it repeatedly swaps adjacent out-of-order items.

Common Mistakes

Mistake: Not reducing inner loop range each pass, causing unnecessary comparisons
Fix: Use 'n-1-i' as inner loop limit to skip already sorted elements

Mistake: Not breaking early when no swaps happen, leading to extra passes
Fix: Add a swapped flag and break if no swaps in a pass

Summary

Bubble sort repeatedly swaps adjacent elements to sort the array.

Use it for small or nearly sorted lists where simplicity matters more than speed.

The key insight is that each pass pushes the largest unsorted element to its correct place at the end.

Practice

1. What is the main idea behind the Bubble Sort algorithm?

easy

A. Repeatedly swap adjacent elements if they are in the wrong order

B. Divide the list into halves and sort each half separately

C. Select the smallest element and move it to the beginning

D. Insert each element into its correct position in a sorted sublist

Solution

1. Step 1: Understand Bubble Sort mechanism

   Bubble Sort compares adjacent elements and swaps them if they are out of order.

2. Step 2: Compare with other sorting methods

   Other options describe different algorithms: divide and conquer, selection sort, insertion sort.

3. Final Answer:

   Repeatedly swap adjacent elements if they are in the wrong order -> Option A

4. Quick Check:

   Bubble Sort = swapping adjacent pairs [OK]

Hint: Bubble Sort swaps neighbors repeatedly until sorted [OK]

Common Mistakes:

• Confusing Bubble Sort with Selection Sort
• Thinking it divides the list like Merge Sort
• Assuming it inserts elements like Insertion Sort

2. Which of the following is the correct way to write the outer loop for Bubble Sort in Go to sort an array arr of length n?

easy

A. for i := 0; i < n-1; i++ {}

B. for i := 0; i < n; i++ {}

C. for i := 1; i <= n; i++ {}

D. for i := 1; i < n-1; i++ {}

Solution

1. Step 1: Determine loop range for passes

   Bubble Sort requires n-1 passes to ensure sorting, so loop runs from 0 to n-2 (i < n-1).

2. Step 2: Check options for correct syntax and range

   for i := 0; i < n-1; i++ {} correctly uses i := 0; i < n-1; i++. Others either run too many or incorrect iterations.

3. Final Answer:

   for i := 0; i < n-1; i++ {} -> Option A

4. Quick Check:

   Outer loop runs n-1 times [OK]

Hint: Outer loop runs n-1 times in Bubble Sort [OK]

Common Mistakes:

• Using i <= n causing out-of-range errors
• Starting loop at 1 instead of 0
• Looping n times instead of n-1

3. What will be the output of the following Go code snippet after applying one full pass of Bubble Sort on the array?

arr := []int{5, 3, 8, 4, 2}
n := len(arr)
for j := 0; j < n-1; j++ {
    if arr[j] > arr[j+1] {
        arr[j], arr[j+1] = arr[j+1], arr[j]
    }
}
fmt.Println(arr)

medium

A. [2 3 4 5 8]

B. [3 5 8 4 2]

C. [3 5 4 2 8]

D. [5 3 8 4 2]

Solution

1. Step 1: Perform one pass of Bubble Sort

   Compare and swap adjacent elements: - Compare 5 & 3: swap -> [3 5 8 4 2] - Compare 5 & 8: no swap - Compare 8 & 4: swap -> [3 5 4 8 2] - Compare 8 & 2: swap -> [3 5 4 2 8]

2. Step 2: Final array after one pass

   After one pass, largest element 8 moves to the end. Array is [3 5 4 2 8].

3. Final Answer:

   [3 5 4 2 8] -> Option C

4. Quick Check:

   One pass moves largest to end [OK]

Hint: One pass pushes largest element to the end [OK]

Common Mistakes:

• Assuming full sort after one pass
• Not swapping correctly
• Confusing indices in swaps

4. Identify the error in the following Bubble Sort code snippet in Go:

arr := []int{4, 2, 7, 1}
n := len(arr)
for i := 0; i < n; i++ {
    for j := 0; j < n; j++ {
        if arr[j] > arr[j+1] {
            arr[j], arr[j+1] = arr[j+1], arr[j]
        }
    }
}
fmt.Println(arr)

medium

A. Outer loop should start from 1 instead of 0

B. Inner loop runs out of range causing runtime error

C. Swap condition should be arr[j] < arr[j+1]

D. Array length n is incorrect

Solution

1. Step 1: Analyze inner loop range

   Inner loop runs j from 0 to n-1, but accesses arr[j+1]. When j = n-1, arr[j+1] is out of range causing runtime error.

2. Step 2: Correct inner loop range

   Inner loop should run from 0 to n-2 (j < n-1) to avoid out-of-range access.

3. Final Answer:

   Inner loop runs out of range causing runtime error -> Option B

4. Quick Check:

   Index out of range error = inner loop limit [OK]

Hint: Inner loop must stop before last index to avoid out-of-range [OK]

Common Mistakes:

• Not adjusting inner loop limit
• Swapping with wrong comparison
• Misunderstanding loop boundaries

5. Given the array arr := []int{3, 1, 4, 5, 2}, how many total swaps will Bubble Sort perform to fully sort the array in ascending order?

hard

A. 5

B. 7

C. 6

D. 4

Solution

1. Step 1: Trace swaps in each pass

   Initial array: [3,1,4,5,2] Pass 1: - 3 > 1 swap -> [1,3,4,5,2] (1 swap) - 3 > 4 no swap - 4 > 5 no swap - 5 > 2 swap -> [1,3,4,2,5] (2 swaps total) Pass 2: - 1 > 3 no swap - 3 > 4 no swap - 4 > 2 swap -> [1,3,2,4,5] (3 swaps total) Pass 3: - 1 > 3 no swap - 3 > 2 swap -> [1,2,3,4,5] (4 swaps total) Pass 4: - 1 > 2 no swap - 2 > 3 no swap No swaps, sorting done.

2. Step 2: Count total swaps

   Pass 1: 2 swaps Pass 2: 1 swap Pass 3: 1 swap Total = 4 swaps Recheck carefully: Pass 1: swaps at (3,1) and (5,2) = 2 Pass 2: swap at (4,2) = 1 Pass 3: swap at (3,2) = 1 Total swaps = 4

3. Step 3: Verify if more swaps needed

   Sorting completes after pass 4 with no swaps. Total swaps = 4

4. Final Answer:

   4 -> Option D

5. Quick Check:

   Count swaps carefully per pass [OK]

Hint: Count swaps each pass until no swaps remain [OK]

Common Mistakes:

• Counting comparisons instead of swaps
• Missing swaps in later passes
• Assuming swaps equal to array length