Bubble Sort Algorithm in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bubble Sort on a small array

What is the output of the following Go code after performing bubble sort on the array?

DSA 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, 1, 4, 2, 8}
    bubbleSort(arr)
    fmt.Println(arr)
}

A [1 2 4 5 8]

B [5 4 2 1 8]

C [8 5 4 2 1]

D [1 4 2 5 8]

💡 Hint

Bubble sort swaps adjacent elements if they are in the wrong order, repeatedly.

The bubble sort algorithm compares adjacent elements and swaps them if the left element is greater than the right. After all passes, the array is sorted in ascending order.

🧠 Conceptual

intermediate

Number of passes in Bubble Sort

For an array of length n, how many passes does the bubble sort algorithm perform in the worst case?

A n passes

B n-1 passes

C n/2 passes

D n+1 passes

💡 Hint

Each pass places the largest unsorted element at the end.

Bubble sort requires n-1 passes to guarantee the array is sorted because each pass places one element in its correct position.

🔧 Debug

advanced

Identify the error in this Bubble Sort implementation

What error will this Go code produce when run?

DSA Go

package main
import "fmt"
func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n; 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{3, 2, 1}
    bubbleSort(arr)
    fmt.Println(arr)
}

A runtime error: index out of range

B [1 2 3]

C no output, infinite loop

D compilation error

💡 Hint

Check the inner loop boundary conditions carefully.

The inner loop runs until j < n-i-1, so arr[j+1] does not access out of range. The original code had j < n-i which caused the runtime error.

🚀 Application

advanced

Optimizing Bubble Sort to stop early

Which modification to the bubble sort algorithm allows it to stop early if the array is already sorted?

A Use recursion instead of loops.

B Reduce the array size by one after each pass without checking swaps.

C Sort only half of the array elements.

D Add a flag to check if any swaps happened in a pass; stop if none.

💡 Hint

If no swaps occur in a pass, the array is sorted.

Adding a boolean flag to detect swaps lets the algorithm stop early, improving efficiency on nearly sorted arrays.

❓ Predict Output

expert

Output of Bubble Sort on a reversed array with duplicates

What is the output of the following Go code after bubble sort is applied?

DSA 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{9, 7, 7, 5, 3, 3, 1}
    bubbleSort(arr)
    fmt.Println(arr)
}

A [9 7 7 5 3 3 1]

B [3 3 5 7 7 9 1]

C [1 3 3 5 7 7 9]

D [1 3 5 7 9]

💡 Hint

Bubble sort sorts all elements including duplicates in ascending order.

The bubble sort correctly sorts the array including duplicates, resulting in ascending order.

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