Selection Sort Algorithm: Step-by-Step Guide with Rust and Go

Selection sort is a simple comparison algorithm that repeatedly finds the smallest value in the unsorted part of an array and moves it to the next sorted position.

For this input:

[13, 46, 24, 52, 20, 9]

the first pass finds 9, swaps it with 13, and produces:

[9, 46, 24, 52, 20, 13]

After that pass, index 0 is finished. The algorithm repeats the same process on the remaining elements.

Selection sort is not the algorithm you would normally choose for a large production dataset. Its value is that it makes several foundational ideas easy to see: maintaining sorted and unsorted regions, scanning for an optimum, using a loop invariant, swapping in place, and deriving time complexity from nested loops.

This article starts the Sorting Algorithms series on krunalkanojiya.com. Every tutorial in the series will explain the algorithm visually, analyze its behavior, and provide implementations in Rust and Go.

What Is Selection Sort?

Selection sort divides an array into two logical regions:

sorted region | unsorted region

At the beginning, the sorted region is empty. During each pass, the algorithm:

1. Treats the first unsorted element as the current minimum.
2. Scans the rest of the unsorted region.
3. Remembers the index of the smallest value found.
4. Swaps that value with the first unsorted element.
5. Moves the boundary one position to the right.

The name comes from this repeated selection of the smallest remaining element.

Selection Sort Algorithm

For an array containing n elements:

for i from 0 to n - 2:
    minimum_index = i

    for j from i + 1 to n - 1:
        if array[j] < array[minimum_index]:
            minimum_index = j

    if minimum_index is not i:
        swap array[i] and array[minimum_index]

The outer loop stops at n - 2. Once the smallest n - 1 elements occupy their correct positions, the final element must also be correct.

The minimum_index != i check avoids writing to the array when the current element is already the smallest one in the remaining region.

Selection Sort Dry Run

Let us sort:

[13, 46, 24, 52, 20, 9]

Pass 1: fill index 0

Start with 13 as the minimum. Compare it with every value to its right. The smallest value is 9 at index 5.

Before: [13, 46, 24, 52, 20, 9]
Swap:    13 <-> 9
After:  [ 9, 46, 24, 52, 20, 13]
          ^ sorted

Pass 2: fill index 1

Search [46, 24, 52, 20, 13]. The minimum is 13.

Before: [9, 46, 24, 52, 20, 13]
Swap:       46 <-> 13
After:  [9, 13, 24, 52, 20, 46]
         sorted

Pass 3: fill index 2

Search [24, 52, 20, 46]. The minimum is 20.

Before: [9, 13, 24, 52, 20, 46]
Swap:           24 <-> 20
After:  [9, 13, 20, 52, 24, 46]
         sorted

Pass 4: fill index 3

Search [52, 24, 46]. The minimum is 24.

Before: [9, 13, 20, 52, 24, 46]
Swap:               52 <-> 24
After:  [9, 13, 20, 24, 52, 46]
         sorted

Pass 5: fill index 4

Search [52, 46]. The minimum is 46.

Before: [9, 13, 20, 24, 52, 46]
Swap:                       52 <-> 46
After:  [9, 13, 20, 24, 46, 52]

The array is sorted after five passes:

[9, 13, 20, 24, 46, 52]

Why Selection Sort Is Correct

A useful way to reason about the algorithm is with a loop invariant: before pass i, the section array[0..i] contains the i smallest input elements in sorted order. The University of Toronto's selection sort course notes formalize the same invariant: the sorted prefix is ordered and no greater than the remaining elements.

We can justify it in three steps:

1. Initialization: Before the first pass, the sorted region is empty, so the claim is true.
2. Maintenance: The pass finds the smallest value in array[i..n] and places it at index i. The sorted region therefore gains the correct next value.
3. Termination: When the loop ends, the first n - 1 positions are correct. The remaining value must be the largest, so the entire array is sorted.

This proof also explains why scanning only part of the unsorted region would break the algorithm: you could not guarantee that the chosen element is the smallest remaining one.

Selection Sort in Rust

The generic Rust version below sorts any mutable slice whose elements implement Ord:

pub fn selection_sort<T: Ord>(values: &mut [T]) {
    let len = values.len();

    for i in 0..len.saturating_sub(1) {
        let mut minimum_index = i;

        for j in (i + 1)..len {
            if values[j] < values[minimum_index] {
                minimum_index = j;
            }
        }

        if minimum_index != i {
            values.swap(i, minimum_index);
        }
    }
}

fn main() {
    let mut numbers = [13, 46, 24, 52, 20, 9];
    selection_sort(&mut numbers);
    println!("{numbers:?}");
}

#[cfg(test)]
mod tests {
    use super::selection_sort;

    #[test]
    fn sorts_integers() {
        let mut values = [13, 46, 24, 52, 20, 9];
        selection_sort(&mut values);
        assert_eq!(values, [9, 13, 20, 24, 46, 52]);
    }

    #[test]
    fn handles_empty_and_duplicate_values() {
        let mut empty: [i32; 0] = [];
        selection_sort(&mut empty);
        assert_eq!(empty, []);

        let mut duplicates = [4, 2, 4, 1, 2];
        selection_sort(&mut duplicates);
        assert_eq!(duplicates, [1, 2, 2, 4, 4]);
    }
}

Why use saturating_sub(1)? Subtracting one directly from a zero-length slice can underflow. Saturating subtraction keeps the result at zero, so the outer range is empty for both empty and single-element inputs.

Rust's swap method safely exchanges the values at two indices without requiring elements to implement Copy; see the official Rust slice documentation.

Selection Sort in Go

With Go generics, we can write one implementation for the common built-in ordered types:

package main

import "fmt"

type Ordered interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
		~float32 | ~float64 | ~string
}

func SelectionSort[T Ordered](values []T) {
	for i := 0; i < len(values)-1; i++ {
		minimumIndex := i

		for j := i + 1; j < len(values); j++ {
			if values[j] < values[minimumIndex] {
				minimumIndex = j
			}
		}

		if minimumIndex != i {
			values[i], values[minimumIndex] = values[minimumIndex], values[i]
		}
	}
}

func main() {
	numbers := []int{13, 46, 24, 52, 20, 9}
	SelectionSort(numbers)
	fmt.Println(numbers)
}

The function changes the underlying slice in place. It does not need to return the slice. Go's multiple assignment makes the swap concise and evaluates both right-hand values before assigning either destination.

A table-driven test covers important cases:

package main

import (
	"reflect"
	"testing"
)

func TestSelectionSort(t *testing.T) {
	tests := []struct {
		name string
		input []int
		want []int
	}{
		{"empty", []int{}, []int{}},
		{"one value", []int{7}, []int{7}},
		{"already sorted", []int{1, 2, 3}, []int{1, 2, 3}},
		{"reverse order", []int{3, 2, 1}, []int{1, 2, 3}},
		{"duplicates", []int{4, 2, 4, 1}, []int{1, 2, 4, 4}},
	}

	for _, test := range tests {
		t.Run(test.name, func(t *testing.T) {
			SelectionSort(test.input)
			if !reflect.DeepEqual(test.input, test.want) {
				t.Fatalf("got %v, want %v", test.input, test.want)
			}
		})
	}
}

Selection Sort Complexity Analysis

Selection sort scans the complete unsorted region during every pass.

The number of comparisons is exact:

(n - 1) + (n - 2) + ... + 2 + 1
= n(n - 1) / 2

For n = 6, selection sort performs:

5 + 4 + 3 + 2 + 1 = 15 comparisons

Standard selection sort performs at most n - 1 swaps. That is fewer writes than algorithms that repeatedly exchange adjacent values, although it does not compensate for quadratic comparisons on large inputs.

Is selection sort adaptive?

No. An adaptive sorting algorithm becomes faster when the input is already or nearly sorted. Selection sort performs the same number of comparisons regardless of initial order.

Is Selection Sort Stable?

The usual swap-based implementation is not stable. Stability means equal keys retain their original relative order.

Consider records where the letter identifies the original order:

[(4, A), (4, B), (2, C)]

The first pass swaps (2, C) with (4, A):

[(2, C), (4, B), (4, A)]

The two records with key 4 have reversed their relative order. This is why standard selection sort is unstable.

A stable variation can remove the minimum and shift every intervening element one position to the right instead of performing a distant swap. That preserves equal-key ordering but increases data movement. If stability is a requirement, using an algorithm designed to be stable is usually clearer.

Common Selection Sort Mistakes

Swapping inside the inner loop

Only update minimum_index while scanning. Swap once after the inner loop finishes.

Forgetting to reset the minimum

Set minimum_index = i at the start of every outer pass. A minimum index from the previous pass no longer describes the new unsorted region.

Comparing with the wrong value

Use:

array[j] < array[minimum_index]

Comparing every candidate only with array[i] can lose track of a smaller value found earlier in the same pass.

Mishandling empty input

Be careful with unsigned indices in Rust. The implementation above prevents subtraction underflow for an empty slice.

Claiming an O(n) best case

The common selection sort implementation does not stop early. Even a sorted input requires n(n - 1) / 2 comparisons.

When Should You Use Selection Sort?

Selection sort is appropriate when:

• You are learning or teaching algorithm fundamentals.
• The collection is very small and implementation simplicity matters.
• Extra memory must remain constant.
• Writes are significantly more expensive than comparisons and the low swap count is useful.
• You need a small, predictable baseline for comparing sorting algorithms.

Avoid it for large or performance-sensitive inputs. Its work grows quadratically: doubling the input size produces roughly four times as many comparisons.

For application code, prefer the standard sorting facilities provided by Rust and Go. They are optimized, well-tested, and clearer about production intent. Go's official slices.Sort documentation, for example, provides the generic standard-library operation for ordered values.

numbers.sort();

slices.Sort(numbers)

Implement selection sort yourself when the implementation is the lesson or when its specific write behavior matches a measured constraint.

Selection Sort vs Bubble Sort

These algorithms are often taught together, but their passes do different work.

Selection sort is attractive when reducing swaps matters. An optimized bubble sort is adaptive, so it can recognize already sorted input. Neither should be the default choice for large general-purpose datasets.

The Bottom Line

Selection sort grows a sorted region one position at a time:

find minimum -> place it at the boundary -> move boundary -> repeat

Its implementation is compact, uses O(1) auxiliary space, and makes at most n - 1 swaps. The trade-off is an exact n(n - 1) / 2 comparisons, giving O(n²) time in the best, average, and worst cases. The standard distant-swap version is also unstable.

The Rust and Go implementations follow the same invariant: before each pass, every position left of i is already final. Understanding that invariant is more valuable than memorizing the code because the same reasoning applies to many in-place algorithms.

Continue with the complete Bubble Sort Algorithm guide and Insertion Sort Algorithm guide, then follow the Sorting Algorithms category as the series expands with merge sort, quicksort, and other developer-focused tutorials.