Selection sort algorithm

Selection sort is another simple sorting algorithm that works by repeatedly finding the minimum/maximum element in the array and swapping it with the current element. The algorithm continues to iterate until the array is sorted.

Algorithm

1. The algorithm takes the array as input.
2. It initializes the first element as the current minimum/maximum element in the array. (let's chose the minimum element for this example)
3. It compares the current minimum with each element in the array.
4. If the current element is smaller than the current minimum, the algorithm swaps them.
5. The current minimum (at the end of the iteration) is swapped with element at the beginning of the array.
6. This goes on till the end of the array.

Now let's write a function that implements the preceding steps:

fn selection_sort(array: Vec<i32>) -> Vec<i32> {
    let mut array = array;
    let arr_len = array.len();
    
    for i in 0..arr_len - 1 {
        let mut current_min = i;
        for current_idx in i + 1..arr_len {
            if array[current_min] > array[current_idx] {
                current_min = current_idx;
            }
        }
        array.swap(current_min, i);
    }
    array
}

Here, we created a function that accepts an array and gives out the sorted array. We used a for loop to iterate over the array. The first for loop is set to iterate N - 1 times, where N is the length of the array. This is because we need to swap every element to its sorted position. The second for loop starts iterating from i + 1 till the end of the array because the elements before i are already sorted. So, in the second loop, we are only comparing N - i elements.

The if condition checks if the current element is smaller than the current minimum. If it is, then we swap them. This is done by using the swap function.

At the end of the function, we return the sorted array.

Result

fn main() {
    let array = vec![45, 7, 12, 33, 19, 48, 26, 36];

    let sorted_array = selection_sort(array);

    println!("Sorted array: {:?}", sorted_array);
}

fn selection_sort(array: Vec<i32>) -> Vec<i32> {
    let mut array = array;
    let arr_len = array.len();
    
    for i in 0..arr_len - 1 {
        let mut current_min = i;
        for current_idx in i + 1..arr_len {
            if array[current_min] > array[current_idx] {
                current_min = current_idx;
            }
        }
        array.swap(current_min, i);
    }
    array
}

Time and Space Complexity

The time complexity of selection sort is O(n^2), where n is the number of elements in the array. This is because the algorithm compares each element with every other element in the array, resulting in quadratic time complexity.

The space complexity of selection sort is O(1), as it does not require any extra space other than the input array itself.