Selection Sort Algorithm in DSA Rust - Execution Trace

Concept Flow - Selection Sort Algorithm

Start with unsorted array

↓

Set i = 0 (start index)

↓

Find min element from i to end

↓

Swap min element with element at i

↓

Increment i

↓

Is i < array length - 1?

No→Sorted array done

↩Back to find min element

Selection Sort repeatedly finds the smallest element in the unsorted part and swaps it to the front, moving the boundary of sorted and unsorted parts forward.

Execution Sample

DSA Rust

let mut arr = [5, 3, 8, 1, 2];
for i in 0..arr.len() - 1 {
    let mut min_idx = i;
    for j in i+1..arr.len() {
        if arr[j] < arr[min_idx] {
            min_idx = j;
        }
    }
    arr.swap(i, min_idx);
}

This code sorts the array by selecting the minimum element from the unsorted part and swapping it with the current position.

Execution Table

Step	Operation	Array State	Comparison	Swap?	Resulting Array
1.1	Set i=0, find min from index 0	[5, 3, 8, 1, 2]	Compare 3 < 5	Yes, min_idx=1	[5, 3, 8, 1, 2]
1.2	Compare 8 < 3	Same	No	No	Same
1.3	Compare 1 < 3	Same	Yes, min_idx=3	No	Same
1.4	Compare 2 < 1	Same	No	No	Same
1.5	Swap arr[0] and arr[3]	Before swap: [5, 3, 8, 1, 2]	Swap	Yes	After swap: [1, 3, 8, 5, 2]
2.1	Set i=1, find min from index 1	[1, 3, 8, 5, 2]	Compare 8 < 3	No	Same
2.2	Compare 5 < 3	Same	No	No	Same
2.3	Compare 2 < 3	Same	Yes, min_idx=4	No	Same
2.4	Swap arr[1] and arr[4]	Before swap: [1, 3, 8, 5, 2]	Swap	Yes	After swap: [1, 2, 8, 5, 3]
3.1	Set i=2, find min from index 2	[1, 2, 8, 5, 3]	Compare 5 < 8	Yes, min_idx=3	Same
3.2	Compare 3 < 5	Same	Yes, min_idx=4	No	Same
3.3	Swap arr[2] and arr[4]	Before swap: [1, 2, 8, 5, 3]	Swap	Yes	After swap: [1, 2, 3, 5, 8]
4.1	Set i=3, find min from index 3	[1, 2, 3, 5, 8]	Compare 8 < 5	No	Same
4.2	Swap arr[3] and arr[3]	Before swap: [1, 2, 3, 5, 8]	Swap	Yes (same element)	After swap: [1, 2, 3, 5, 8]
5	i=4, loop ends	[1, 2, 3, 5, 8]	No more elements to compare	No	Sorted array done

💡 i reaches 4, which is array length - 1, so sorting is complete

Variable Tracker

Variable	Start	After Step 1.5	After Step 2.4	After Step 3.3	After Step 4.2	Final
i	0	1	2	3	4	4
min_idx	0	3	4	4	3	3
Array	[5, 3, 8, 1, 2]	[1, 3, 8, 5, 2]	[1, 2, 8, 5, 3]	[1, 2, 3, 5, 8]	[1, 2, 3, 5, 8]	[1, 2, 3, 5, 8]

Key Moments - 3 Insights

Why do we swap even when the minimum element is already at the current index?

In step 4.2, the minimum element is at index 3 itself, so swapping arr[3] with arr[3] does nothing but keeps the algorithm consistent. This is shown in execution_table row 4.2.

Why do we only loop until i < array length - 1?

Because after placing the smallest elements up to the second last position, the last element must be in correct place. The loop ends at i=4 (array length -1) as shown in exit_note.

How do we know which element is the minimum during the inner loop?

We track min_idx and update it whenever we find a smaller element during comparisons, as shown in execution_table rows like 1.3 and 2.3.

Visual Quiz - 3 Questions

Look at the execution_table at step 2.3, what is the value of min_idx?

A 4

B 1

C 3

D 2

💡 Hint

Check the 'Comparison' and 'Swap?' columns at step 2.3 where min_idx is updated.

At which step does the array first become sorted up to the third element?

A After step 2.4

B After step 3.3

C After step 1.5

D After step 4.2

💡 Hint

Look at the 'Resulting Array' column to see when the first three elements are in ascending order.

If we skip the swap operation at step 1.5, what would be the array state after step 1.5?

A [5, 2, 8, 1, 3]

B [1, 3, 8, 5, 2]

C [5, 3, 8, 1, 2]

D [1, 2, 8, 5, 3]

💡 Hint

Skipping swap at step 1.5 means the first element remains 5; check how that affects subsequent steps.

Concept Snapshot

Selection Sort Algorithm:
- Loop from i=0 to n-2
- Find minimum element index from i to end
- Swap minimum element with element at i
- Repeat until array is sorted
- Time complexity: O(n²), in-place sorting

Full Transcript

Selection Sort works by dividing the array into sorted and unsorted parts. Starting at index 0, it finds the smallest element in the unsorted part and swaps it with the element at the current index. This process repeats by moving the boundary forward until the entire array is sorted. The execution table shows each comparison and swap step, tracking how the array changes. Variables like i and min_idx help track positions. Even when the minimum element is already at the current index, a swap occurs for consistency. The loop ends when i reaches the second last index because the last element is then sorted by default.

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