Go Program to Perform Selection Sort on an Array

A Go program for selection sort uses nested for loops to find the smallest element and swap it with the current position; for example, for i := 0; i < len(arr)-1; i++ { minIdx := i; for j := i+1; j < len(arr); j++ { if arr[j] < arr[minIdx] { minIdx = j } } arr[i], arr[minIdx] = arr[minIdx], arr[i] } sorts the array in place.

Examples

Input[5, 3, 8, 4, 2]

Output[2 3 4 5 8]

Input[1, 2, 3, 4, 5]

Output[1 2 3 4 5]

Input[9]

Output[9]

How to Think About It

To sort an array using selection sort, think of dividing the list into two parts: sorted and unsorted. Start from the first element, find the smallest element in the unsorted part, and swap it with the first element. Repeat this for each position until the whole array is sorted.

Algorithm

1

Start from the first element of the array.

2

Find the smallest element in the unsorted part of the array.

3

Swap the smallest element with the current element.

4

Move to the next element and repeat until the array is sorted.

Code

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, 3, 8, 4, 2}
    selectionSort(arr)
    fmt.Println(arr)
}

Output

[2 3 4 5 8]

Dry Run

Let's trace the array [5, 3, 8, 4, 2] through the selection sort code.

1

First pass (i=0)

Find smallest from index 0 to end: smallest is 2 at index 4; swap arr[0] and arr[4]. Array becomes [2, 3, 8, 4, 5].

2

Second pass (i=1)

Find smallest from index 1 to end: smallest is 3 at index 1; swap arr[1] and arr[1]. Array stays [2, 3, 8, 4, 5].

3

Third pass (i=2)

Find smallest from index 2 to end: smallest is 4 at index 3; swap arr[2] and arr[3]. Array becomes [2, 3, 4, 8, 5].

4

Fourth pass (i=3)

Find smallest from index 3 to end: smallest is 5 at index 4; swap arr[3] and arr[4]. Array becomes [2, 3, 4, 5, 8].

Pass	Array State
1	[2 3 8 4 5]
2	[2 3 8 4 5]
3	[2 3 4 8 5]
4	[2 3 4 5 8]

Why This Works

Step 1: Finding the smallest element

The inner loop uses if arr[j] < arr[minIdx] to find the smallest element in the unsorted part.

Step 2: Swapping elements

After finding the smallest element, it swaps with the current position using arr[i], arr[minIdx] = arr[minIdx], arr[i] to place it correctly.

Step 3: Repeating for all elements

The outer loop moves the boundary of the sorted part forward until the entire array is sorted.

Alternative Approaches

Bubble Sort

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

Bubble sort repeatedly swaps adjacent elements; simpler but often slower than selection sort.

Insertion Sort

go

package main

import "fmt"

func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        key := arr[i]
        j := i - 1
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
}

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

Insertion sort builds the sorted array one element at a time; efficient for nearly sorted data.

Complexity: O(n^2) time, O(1) space

Time Complexity

Selection sort uses two nested loops each running up to n times, resulting in O(n^2) time complexity regardless of input order.

Space Complexity

It sorts the array in place using only a few extra variables, so space complexity is O(1).

Which Approach is Fastest?

Selection sort is simple but slower than efficient algorithms like quicksort or mergesort; bubble and insertion sorts are similar in speed but differ in behavior.

Approach	Time	Space	Best For
Selection Sort	O(n^2)	O(1)	Small arrays, simple implementation
Bubble Sort	O(n^2)	O(1)	Teaching sorting basics, nearly sorted data
Insertion Sort	O(n^2)	O(1)	Nearly sorted arrays, small datasets