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.