Selection Sort Algorithm in DSA Go

Mental Model

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

Analogy: Imagine picking the smallest apple from a basket and placing it in a new row, then picking the next smallest from the remaining apples, and so on.

[7, 3, 5, 2, 4]
 ↑
(minIndex points here)

Dry Run Walkthrough

Input: list: [7, 3, 5, 2, 4]

Goal: Sort the list in ascending order using selection sort

Step 1: Find smallest from index 0 to end and swap with index 0

[2, 3, 5, 7, 4]
 ↑

Why: Put smallest value 2 at the start

Step 2: Find smallest from index 1 to end and swap with index 1

[2, 3, 5, 7, 4]
    ↑

Why: 3 is already smallest in remaining, no change

Step 3: Find smallest from index 2 to end and swap with index 2

[2, 3, 4, 7, 5]
       ↑

Why: Swap 4 with 5 to put next smallest in place

Step 4: Find smallest from index 3 to end and swap with index 3

[2, 3, 4, 5, 7]
          ↑

Why: Swap 5 with 7 to continue sorting

Step 5: Last element is in place, sorting done

[2, 3, 4, 5, 7]

Why: All elements sorted

Result:

[2, 3, 4, 5, 7]

Annotated Code

DSA Go

package main

import "fmt"

func selectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; 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]
    }
}

func main() {
    arr := []int{7, 3, 5, 2, 4}
    selectionSort(arr)
    fmt.Println(arr)
}

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

iterate over each position to place the smallest remaining element

minIndex := i

assume current position holds the smallest value

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

search the rest of the array for a smaller value

if arr[j] < arr[minIndex] { minIndex = j }

update minIndex if a smaller element is found

arr[i], arr[minIndex] = arr[minIndex], arr[i]

swap smallest found with current position

Output

[2 3 4 5 7]

Complexity Analysis

Time: O(n^2) because for each element we scan the rest to find the smallest

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

vs Alternative: Compared to bubble sort, selection sort does fewer swaps but still has O(n^2) comparisons

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++ {

array with all elements equal

no swaps occur, array stays unchanged

DSA Go

if arr[j] < arr[minIndex] { minIndex = j }

When to Use This Pattern

When you need a simple sorting method that repeatedly selects the smallest item and places it in order, use selection sort because it clearly separates finding minimum and swapping.

Common Mistakes

Mistake: Swapping inside the inner loop instead of after finding the minimum
Fix: Only swap once per outer loop iteration after the minimum is found

Summary

Selection sort repeatedly finds the smallest element and moves it to the front.

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

The key insight is to separate finding the minimum from swapping to reduce unnecessary swaps.