Selection Sort in Rust: A Comprehensive Guide

Sorting algorithms are essential for understanding computer science and solving numerous practical problems. Among them, Selection Sort stands out as a straightforward algorithm, often used for educational purposes due to its simplicity. In this article, we’ll explore how to implement Selection Sort in Rust, a language known for its performance and memory safety.

What is the Selection Sort?

Selection Sort is a comparison-based sorting algorithm that divides the input list into two parts: a sorted section and an unsorted section. It repeatedly selects the smallest (or largest) element from the unsorted section and moves it to the sorted section.

Algorithm Overview

1. Iterate through the list.

2. For each element, find the smallest element in the unsorted portion.

3. Swap the smallest element with the current element.

4. Move to the next element and repeat until the list is sorted.

The algorithm has a time complexity of O(n²), making it inefficient for large datasets. However, its simplicity and predictability make it suitable for small lists and educational purposes.

Implementing Selection Sort in Rust

Let’s implement the Selection Sort algorithm in Rust. The goal is to sort a vector of elements that implement the Ord trait in ascending order.

fn selection_sort<T: Ord>(arr: &mut Vec<T>) {
    let n = arr.len();

    for i in 0..n {
        // Assume the current index is the smallest
        let mut min_index = i;

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

        // Swap the smallest element with the current element
        if min_index != i {
            arr.swap(i, min_index);
        }
    }
}

fn main() {
    let mut numbers = vec![64, 25, 12, 22, 11];
    println!("Before sorting: {:?}", numbers);

    selection_sort(&mut numbers);

    println!("After sorting: {:?}", numbers);

    let mut words = vec!["pear", "apple", "orange", "banana"];
    println!("Before sorting: {:?}", words);

    selection_sort(&mut words);

    println!("After sorting: {:?}", words);
}

Explanation

1. Outer Loop: Iterates through the vector, treating each position as the starting point for the unsorted section.

2. Inner Loop: Searches for the smallest element in the unsorted portion of the vector.

3. Swap Operation: Uses Rust’s built-in swap method to exchange elements, ensuring memory safety and performance.

Testing the Implementation

Separate Testing Module

In Rust, tests are usually implemented in a separate module annotated with #[cfg(test)]. This keeps the testing code isolated from the main implementation, improving readability and organization. Below is an example:

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

    #[test]
    fn test_empty_array() {
        let mut arr: Vec<i32> = vec![];
        selection_sort(&mut arr);
        assert_eq!(arr, vec![]);
    }

    #[test]
    fn test_single_element() {
        let mut arr = vec![1];
        selection_sort(&mut arr);
        assert_eq!(arr, vec![1]);
    }

    #[test]
    fn test_sorted_array() {
        let mut arr = vec![1, 2, 3, 4, 5];
        selection_sort(&mut arr);
        assert_eq!(arr, vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_reverse_sorted_array() {
        let mut arr = vec![5, 4, 3, 2, 1];
        selection_sort(&mut arr);
        assert_eq!(arr, vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_unsorted_array() {
        let mut arr = vec![64, 25, 12, 22, 11];
        selection_sort(&mut arr);
        assert_eq!(arr, vec![11, 12, 22, 25, 64]);
    }

    #[test]
    fn test_duplicates() {
        let mut arr = vec![3, 3, 2, 1, 1];
        selection_sort(&mut arr);
        assert_eq!(arr, vec![1, 1, 2, 3, 3]);
    }
}

Running the Tests

To run the tests, use the cargo test command. Rust will automatically detect the test module and execute the test cases. Successful tests will confirm the correctness of your implementation.

Advantages of Using Rust

Rust’s safety features ensure that common issues like buffer overflows or null pointer dereferencing are avoided. The Vec type in Rust provides dynamic arrays with built-in methods like swap, making the implementation concise and reliable.

Limitations of Selection Sort

• Inefficiency: With a time complexity of O(n²), Selection Sort is impractical for large datasets.

• Stability: Selection Sort is not a stable sorting algorithm, meaning it does not preserve the relative order of equal elements.

When to Use Selection Sort

Selection Sort is best suited for:

• Small datasets.

• Situations where memory usage is critical, as it operates in-place with O(1) auxiliary space.

• Educational purposes to illustrate sorting algorithms.

Conclusion

In this article, we implemented Selection Sort in Rust and explored its workings. While it’s not the most efficient sorting algorithm, it’s an excellent tool for understanding fundamental sorting concepts and practicing Rust programming. For larger datasets, consider more efficient algorithms like QuickSort or MergeSort.