Selection Sort Algorithm in DSA Rust

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.

Unsorted array:
[7, 3, 5, 2, 4]

Pointers:
start ↑

We look for the smallest from start to end.

Dry Run Walkthrough

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

Goal: Sort the array in ascending order using selection sort

Step 1: Find smallest from index 0 to end; smallest is 2 at index 3; swap with element at index 0

[2, 3, 5, 7, 4]

Why: Put the smallest element at the start to begin sorting

Step 2: Find smallest from index 1 to end; smallest is 3 at index 1; swap with element at index 1 (no change)

[2, 3, 5, 7, 4]

Why: Next smallest is already in place

Step 3: Find smallest from index 2 to end; smallest is 4 at index 4; swap with element at index 2

[2, 3, 4, 7, 5]

Why: Place next smallest in correct position

Step 4: Find smallest from index 3 to end; smallest is 5 at index 4; swap with element at index 3

[2, 3, 4, 5, 7]

Why: Place next smallest in correct position

Step 5: Only one element left at index 4; no action needed

[2, 3, 4, 5, 7]

Why: Last element is already sorted

Result:

Sorted array:
[2, 3, 4, 5, 7]

Annotated Code

DSA Rust

fn selection_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n {
        let mut min_index = i;
        for j in (i + 1)..n {
            if arr[j] < arr[min_index] {
                min_index = j; // update min_index when smaller element found
            }
        }
        arr.swap(i, min_index); // swap smallest found with current position
    }
}

fn main() {
    let mut data = [7, 3, 5, 2, 4];
    selection_sort(&mut data);
    println!("{:?}", data);
}

for i in 0..n {

iterate over each position to place the smallest element

for j in (i + 1)..n {

search for the smallest element in the unsorted part

if arr[j] < arr[min_index] { min_index = j; }

update min_index when a smaller element is found

arr.swap(i, min_index);

swap the smallest element found with the element at current position

Output

[2, 3, 4, 5, 7]

Complexity Analysis

Time: O(n²) 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 same number of comparisons

Edge Cases

empty array

function returns immediately without error

DSA Rust

for i in 0..n {

array with one element

no swaps needed, array remains same

DSA Rust

for i in 0..n {

array with all elements equal

no swaps needed, array remains same

DSA Rust

if arr[j] < arr[min_index] {

When to Use This Pattern

When you need a simple, in-place sorting method and can afford O(n²) time, selection sort is a good first choice because it clearly separates sorted and unsorted parts.

Common Mistakes

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

Mistake: Not updating the min_index when a smaller element is found
Fix: Update min_index inside the inner loop when a smaller element is found

Summary

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

Use it when you want a simple, in-place sort and the data size is small.

The key insight is to separate the array into sorted and unsorted parts and pick the smallest from unsorted each time.

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 sort each half separately

C. Swap adjacent elements if they are in wrong order

D. Insert each element into its correct position in a sorted sublist

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 options

   Repeatedly find the smallest element and move it to the front matches this description exactly, others describe different sorting methods.

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 smallest next element [OK]

Common Mistakes:

• Confusing selection sort with bubble sort
• Thinking it divides list into halves
• Mixing it up with insertion sort

2. Which of the following is the correct Rust syntax to swap two elements a[i] and a[min_index] in a vector a?

easy

A. a.swap_elements(i, min_index);

B. swap(a[i], a[min_index]);

C. a[i], a[min_index] = a[min_index], a[i];

D. a.swap(i, min_index);

Solution

1. Step 1: Recall Rust vector swap method

   Rust vectors have a method called swap that takes two indices and swaps their elements.

2. Step 2: Match syntax with options

   a.swap(i, min_index); uses a.swap(i, min_index); which is correct. Others are invalid Rust syntax or methods.

3. Final Answer:

   a.swap(i, min_index); -> Option D

4. Quick Check:

   Rust vector swap method = a.swap(i, j) [OK]

Hint: Use vector.swap(index1, index2) to swap elements [OK]

Common Mistakes:

• Trying to swap elements directly with assignment
• Using non-existent swap_elements method
• Using Python-style tuple swap syntax

3. What will be the output vector after running selection sort on vec![3, 1, 4, 2]?

medium

A. [1, 3, 2, 4]

B. [4, 3, 2, 1]

C. [1, 2, 3, 4]

D. [2, 1, 3, 4]

Solution

1. Step 1: Perform selection sort step-by-step

   Initial vector: [3, 1, 4, 2] - Find smallest (1), swap with first element: [1, 3, 4, 2] - Find smallest in remaining (3,4,2) is 2, swap with second element: [1, 2, 4, 3] - Find smallest in last two (4,3) is 3, swap with third element: [1, 2, 3, 4]

2. Step 2: Confirm final sorted vector

   The vector is sorted ascending: [1, 2, 3, 4]

3. Final Answer:

   [1, 2, 3, 4] -> Option C

4. Quick Check:

   Selection sort output = sorted ascending [OK]

Hint: Selection sort outputs sorted ascending list [OK]

Common Mistakes:

• Confusing selection sort with reverse sorting
• Stopping after first swap
• Not swapping correctly

4. Consider this Rust code snippet for selection sort. What is the bug?

fn selection_sort(a: &mut Vec<i32>) {
    let n = a.len();
    for i in 0..=n {
        let mut min_index = i;
        for j in i+1..n {
            if a[j] < a[min_index] {
                min_index = j;
            }
        }
        a.swap(i, min_index);
    }
}

medium

A. min_index should be initialized to 0, not i

B. The outer loop should run until n-1, not n

C. The swap method does not exist for vectors

D. The inner loop should start from 0, not i+1

Solution

1. Step 1: Analyze loop ranges

   The outer loop runs from 0 to n inclusive, meaning it runs n+1 times. But the last element does not need to be checked because it will already be sorted.

2. Step 2: Correct loop range for outer loop

   The outer loop should run from 0 to n-1 to avoid unnecessary iteration and potential out-of-bound errors.

3. Final Answer:

   The outer loop should run until n-1, not n -> Option B

4. Quick Check:

   Outer loop range = 0..n-1 [OK]

Hint: Outer loop runs to n-1, not n [OK]

Common Mistakes:

• Running outer loop one step too far
• Starting inner loop incorrectly
• Misunderstanding swap method existence

5. You want to sort a vector of integers but only partially: you want the first 3 smallest elements sorted at the front, and the rest can remain unsorted. How can you modify selection sort to do this efficiently?

hard

A. Run the outer loop only 3 times instead of full length

B. Run the inner loop only 3 times for each outer iteration

C. Sort the entire vector then shuffle last elements randomly

D. Use bubble sort for first 3 elements and selection sort for rest

Solution

1. Step 1: Understand partial sorting requirement

   We only want the first 3 smallest elements sorted at the front, so we only need to find and place the smallest element 3 times.

2. Step 2: Modify selection sort outer loop

   By running the outer loop 3 times, selection sort will place the 3 smallest elements in order at the front, leaving the rest unsorted.

3. Final Answer:

   Run the outer loop only 3 times instead of full length -> Option A

4. Quick Check:

   Partial sort = limit outer loop iterations [OK]

Hint: Limit outer loop to number of elements to sort [OK]

Common Mistakes:

• Modifying inner loop instead of outer loop
• Sorting entire vector unnecessarily
• Mixing sorting algorithms incorrectly