Selection Sort

Selection sort is another fundamental comparison-based algorithm that builds a sorted list by repeatedly selecting the smallest remaining element and placing it in its correct position. While still inefficient for large datasets, it provides an excellent introduction to searching for minimum values, index tracking, and in-place swaps.

Example Walk-through

Let’s sort this array:

[29, 10, 14, 37, 13]

Selection sort works by scanning the unsorted portion of the list, finding the minimum value, and swapping it into its correct position.

Pass 1 - find the minimum from index 0 to end

Unsorted: [29, 10, 14, 37, 13] Minimum value is 10 at index 1.

Swap 29 and 10 → [10, 29, 14, 37, 13]

Pass 2 - find the minimum from index 1 to end

Unsorted: [29, 14, 37, 13] Minimum value is 13 at index 4.

Swap 29 and 13 → [10, 13, 14, 37, 29]

Pass 3 - find the minimum from index 2 to end

Unsorted: [14, 37, 29] Minimum value is already at index 2 → no swap.

Array remains: [10, 13, 14, 37, 29]

Pass 4 - find the minimum from index 3 to end

Unsorted: [37, 29] Minimum is 29 at index 4.

Swap 37 and 29 → [10, 13, 14, 29, 37]

At this point, the array is sorted. Selection sort always performs the same number of passes and comparisons, regardless of how sorted the input is.

Rust Implementation

Below is an idiomatic in-place selection sort implementation. It tracks the index of the smallest value during each pass and performs a single swap at the end of that pass.

pub fn selection_sort(arr: &mut [i32]) {
    let n = arr.len();

    for i in 0..n {
        let mut min_index = i;

        // Find the index of the smallest element in the remaining slice
        for j in (i + 1)..n {
            if arr[j] < arr[min_index] {
                min_index = j;
            }
        }

        // Swap the found minimum with the first unsorted position
        if min_index != i {
            arr.swap(i, min_index);
        }
    }
}

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

    #[test]
    fn it_sorts() {
        let mut input = vec![29, 10, 14, 37, 13];
        selection_sort(&mut input);
        assert_eq!(input, vec![10, 13, 14, 29, 37]);
    }
}

Example Usage

fn main() {
    let mut values = vec![64, 25, 12, 22, 11];
    selection_sort(&mut values);
    println!("{:?}", values); // [11, 12, 22, 25, 64]
}

Time and Space Complexity

Selection sort is simple and predictable. Unlike bubble sort, the number of comparisons is always the same regardless of how sorted the list already is.

Case	Time Complexity	Order of Growth	Reason
Best	O(n²)	Quadratic	Still must scan the unsorted portion to find the minimum each pass.
Average	O(n²)	Quadratic	Typically must search the entire remainder of the list for each index.
Worst	O(n²)	Quadratic	Maximum comparisons required every pass; no early stopping is possible.

Space Complexity

Space	Complexity	Order of Growth	Reason
Auxiliary space	O(1)	Constant	Sorting is performed in-place with only a few additional tracking variables used.

Playground Links

If you’d like to experiment with the full implementation, explore variations, or test additional inputs, you can use the interactive playground links below. Each link contains the complete runnable code for this tutorial.

Rust - Selection Sort

These external playgrounds allow you to:

Modify the algorithm logic
Try different input arrays
Debug step-by-step
Compare behavior with other sorting algorithms