Selection sort

Selection sort is a straightforward, iterative algorithm that repeatedly identifies and relocates the smallest unsorted element within a portion of the array, moving it to the front of the remaining unsorted section until the entire array is in order:

use super::AlgorithmState;

/// Sorts the slice using selection sort algorithm and the comparison function `is_less` passed as
/// argument.
fn selection_sort<T, F>(v: &mut [T], mut is_less: F)
where
    F: FnMut(&T, &T) -> bool,
{
    for i in 0..v.len() {
        let mut k = i;
        for j in i + 1..v.len() {
            if is_less(&v[j], &v[k]) {
                k = j;
            }
        }
        v.swap(i, k);

Is easy to see from the code that the algorithm for each $i$ from $0$ to $N-1$ there is only one swap and $N-1-i$ comparisons, so the total is:

$$(N-1)+(N-2)+\cdots +2+1=\sum _{i=1}^{n-1}i$$ $$\sum _{i=1}^{n-1}i=\frac{(n-1)+1}{2}(n-1)=\frac{1}{2}n(n-1)=\frac{1}{2}(n^2-n)$$

Which is of complexity $$O(n^2)$$ in terms of number of comparisons. Here is an animated image of the visualization of how the algorithm works:

The full source code can be found here