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.

Practice

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

easy

A. Repeatedly find the smallest element and move it to the front

B. Divide the list into halves and merge sorted halves

C. Swap adjacent elements if they are in wrong order repeatedly

D. Use a pivot to partition the list into smaller parts

Solution

1. Step 1: Understand selection sort process

   Selection sort finds the smallest element in the unsorted part and swaps it with the first unsorted element.

2. Step 2: Compare with other sorting methods

   Other options describe merge sort, bubble sort, and quicksort, which are different algorithms.

3. Final Answer:

   Repeatedly find the smallest element and move it to the front -> Option A

4. Quick Check:

   Selection sort = find smallest and swap [OK]

Hint: Selection sort always picks the smallest next element [OK]

Common Mistakes:

• Confusing selection sort with bubble sort
• Thinking it divides list like merge sort
• Assuming it uses a pivot like quicksort

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

easy

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

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

C. for i := 0; i <= n; i++ {

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

Solution

1. Step 1: Understand loop range for selection sort

   The outer loop runs from 0 to n-2 because the last element will be sorted automatically after previous passes.

2. Step 2: Check each option's correctness

   for i := 0; i < n-1; i++ { uses i < n-1, which is correct. Others either go out of bounds or start at wrong index.

3. Final Answer:

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

4. Quick Check:

   Outer loop runs 0 to n-2 [OK]

Hint: Outer loop stops at n-2 because last element is sorted [OK]

Common Mistakes:

• Using <= n causing index out of range
• Starting loop at 1 instead of 0
• Loop running too many times

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

arr := []int{29, 10, 14, 37, 13}
n := len(arr)
minIndex := 0
for j := 1; j < n; j++ {
    if arr[j] < arr[minIndex] {
        minIndex = j
    }
}
arr[0], arr[minIndex] = arr[minIndex], arr[0]
fmt.Println(arr)

medium

A. [10 13 14 37 29]

B. [13 10 14 37 29]

C. [29 10 14 37 13]

D. [10 29 14 37 13]

Solution

1. Step 1: Find minimum element index in full array

   Minimum element is 10 at index 1, so minIndex = 1.

2. Step 2: Swap arr[0] and arr[minIndex]

   Swap arr[0] (29) with arr[1] (10), resulting in [10 29 14 37 13].

3. Final Answer:

   [10 29 14 37 13] -> Option D

4. Quick Check:

   First pass places smallest element at front [OK]

Hint: First pass swaps smallest element to front [OK]

Common Mistakes:

• Not swapping elements after finding minimum
• Confusing minIndex with current index
• Printing array before swap

4. Identify the error in the following Go code implementing selection sort:

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

medium

A. Swap should be done only if minIndex != i

B. minIndex should be initialized outside the outer loop

C. Inner loop condition should be j < n, not j <= n

D. Outer loop should run from i := 1 to n-1

Solution

1. Step 1: Check inner loop boundary

   Inner loop uses j <= n, which causes index out of range error because valid indices are 0 to n-1.

2. Step 2: Correct inner loop condition

   It should be j < n to stay within array bounds.

3. Final Answer:

   Inner loop condition should be j < n, not j <= n -> Option C

4. Quick Check:

   Array indices go from 0 to n-1 [OK]

Hint: Array indices end at n-1, not n [OK]

Common Mistakes:

• Using <= n causing runtime panic
• Initializing minIndex outside outer loop
• Unnecessary swap checks

5. Given the array arr := []int{64, 25, 12, 22, 11}, after how many swaps will the array be fully sorted using selection sort, and what will be the final sorted array?

hard

A. 4 swaps; [11 12 22 25 64]

B. 5 swaps; [11 12 22 25 64]

C. 4 swaps; [64 25 12 22 11]

D. 3 swaps; [11 12 22 25 64]

Solution

1. Step 1: Count swaps in each selection sort pass

   Pass 1: swap 64 and 11 -> [11 25 12 22 64]
   Pass 2: swap 25 and 12 -> [11 12 25 22 64]
   Pass 3: swap 25 and 22 -> [11 12 22 25 64]
   Pass 4: swap 25 and 25 (no change, but swap counted as 1)
   Total swaps = 4 (last swap is with itself, usually counted as swap)

2. Step 2: Final sorted array

   The array after sorting is [11 12 22 25 64].

3. Final Answer:

   4 swaps; [11 12 22 25 64] -> Option A

4. Quick Check:

   Selection sort swaps once per pass, total n-1 swaps [OK]

Hint: Selection sort swaps once per pass, total n-1 swaps [OK]

Common Mistakes:

• Counting swaps incorrectly when swapping element with itself
• Assuming more swaps than passes
• Confusing sorted array with original