Selection Sort Algorithm in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Selection Sort on a small array

What is the output of the following Go code after running selection sort on the array?

DSA Go

package main
import "fmt"
func selectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        minIdx := i
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIdx] {
                minIdx = j
            }
        }
        arr[i], arr[minIdx] = arr[minIdx], arr[i]
    }
}
func main() {
    arr := []int{64, 25, 12, 22, 11}
    selectionSort(arr)
    fmt.Println(arr)
}

A [11 22 12 25 64]

B [64 25 12 22 11]

C [11 12 22 25 64]

D [25 12 22 11 64]

💡 Hint

Selection sort finds the smallest element and puts it at the start, then repeats for the rest.

Selection sort repeatedly selects the smallest element from the unsorted part and swaps it with the first unsorted element. After sorting, the array is in ascending order.

🧠 Conceptual

intermediate

Number of swaps in Selection Sort

How many swaps does selection sort perform on an array of length n in the worst case?

A 0 swaps

B n * (n - 1) / 2 swaps

C n swaps

D n - 1 swaps

💡 Hint

Selection sort swaps only once per outer loop iteration.

Selection sort performs exactly one swap per iteration of the outer loop, so total swaps are n - 1.

🔧 Debug

advanced

Identify the error in this selection sort implementation

What error will this Go code produce when running selection sort?

DSA Go

package main
import "fmt"
func selectionSort(arr []int) {
    n := len(arr)
    for i := 0; i <= n-1; i++ {
        minIdx := i
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIdx] {
                minIdx = j
            }
        }
        arr[i], arr[minIdx] = arr[minIdx], arr[i]
    }
}
func main() {
    arr := []int{3, 1, 2}
    selectionSort(arr)
    fmt.Println(arr)
}

A [1 2 3]

B Index out of range runtime error

C Compilation error: missing import

D [3 1 2]

💡 Hint

Check the loop conditions carefully.

The loop condition i <= n-1 is valid because i goes from 0 to n-1 inclusive. The code runs correctly and sorts the array.

❓ Predict Output

advanced

Selection Sort on a reversed array

What is the output of the following Go code after sorting the reversed array?

DSA Go

package main
import "fmt"
func selectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        minIdx := i
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIdx] {
                minIdx = j
            }
        }
        arr[i], arr[minIdx] = arr[minIdx], arr[i]
    }
}
func main() {
    arr := []int{5, 4, 3, 2, 1}
    selectionSort(arr)
    fmt.Println(arr)
}

A [1 3 2 4 5]

B [1 2 3 4 5]

C [5 4 3 2 1]

D [2 1 3 4 5]

💡 Hint

Selection sort always sorts ascending regardless of input order.

Selection sort finds the smallest element and places it at the front, so the reversed array becomes sorted ascending.

🧠 Conceptual

expert

Time complexity of Selection Sort

What is the time complexity of selection sort in all cases?

A O(n^2) in best, average, and worst cases

B O(n log n) in best case, O(n^2) in worst case

C O(n) in best case, O(n^2) in worst case

D O(n) in all cases

💡 Hint

Selection sort always scans the entire unsorted part to find the minimum.

Selection sort always performs n*(n-1)/2 comparisons regardless of input order, so time complexity is O(n^2) in all cases.