Selection Sort Algorithm in Rust

1. Introduction

The Selection Sort algorithm is a simple in-place comparison sort. The core idea behind selection sort is dividing the list into a sorted and an unsorted part. The leftmost part of the array is considered sorted, while the right part is unsorted. In each iteration, the smallest (or largest, depending on sorting order) element from the unsorted section is selected and swapped with the leftmost unsorted element, placing it in its correct position.

2. Implementation Steps

1. Start with the first position as the current minimum.

2. For each position in the array, compare its value to the current minimum.

3. If a smaller value is found, set this new value as the current minimum.

4. Once the end of the list is reached, swap the current minimum with the first position in the unsorted section.

5. Move to the next position and repeat steps 2-4 until the entire list is sorted.

3. Implementation in Rust Programming

fn selection_sort<T: Ord>(arr: &mut [T]) {
    let len = arr.len();
    for i in 0..len {
        // Assume the current index is the minimum
        let mut min_index = i;
        for j in (i+1)..len {
            // Find the minimum value's index in the unsorted section
            if arr[j] < arr[min_index] {
                min_index = j;
            }
        }
        // Swap the found minimum with the current index
        arr.swap(i, min_index);
    }
}
fn main() {
    let mut numbers = [8, 2, 4, 9, 3, 6];
    selection_sort(&mut numbers);
    println!("{:?}", numbers); // Prints: [2, 3, 4, 6, 8, 9]
}

Output:

[2, 3, 4, 6, 8, 9]

Explanation:

1. We define the selection_sort function that operates on slices of data that can be ordered (Ord).

2. The outer loop (i) goes through each position in the array, which is the starting point for the unsorted section.

3. For each iteration of the outer loop, we initially consider the element at the current position as the minimum.

4. The inner loop (j) traverses the unsorted part of the array to find the index of the minimum value.

5. Once the minimum value's index is determined, we swap it with the value at the current position.

6. This process continues until the entire list is sorted.