Insertion sort in Rust

Question

Here is the code:

pub fn insertion_sort<T>(vec: &mut Vec<T>) where T: Ord + Copy {
    fn insert<U>(vec: &mut Vec<U>, pos: usize, value: U) where U: Ord + Copy {
        assert!(pos > 0);
        let mut pos: usize = pos - 1;
        loop {
            let value_at_pos = vec[pos]; 
            if value_at_pos <= value {
                break;
            }
            vec[pos + 1] = value_at_pos; 
            if pos == 0 {
                vec[pos] = value;
                return ();
            }
            pos -= 1;
        }
        vec[pos + 1] = value;
    }
    for i in 1..vec.len() {
        let value = vec[i];
        insert(vec, i, value);
    }
}

#[test]
fn test_insertion_sort() {
    let mut vec = vec![9, 8, 7, 11, 10]; 
    insertion_sort(&mut vec);
    let vec_res: Vec<_> = (7..12).collect();
    assert_eq!(vec, vec_res);
}

It's slightly more complex than in textbooks due to the fact negative integers are not allowed for indexing in Rust, not a huge problem though.

Answer 1

1. As you have already been made aware, you should not be using &mut Vec<T> unless you plan on adding or removing items from the Vec. Using &mut [T] better expresses the contract of the function and is more flexible, allowing you to also sort arrays and anything else that can be expressed as a slice.

2. where clauses go on a separate line. This allows them to be easily found, which is important considering how much they affect the behavior of the function.

3. There's no need to declare the type of pos. Type inference will take care of it.

4. There's no need to redeclare pos just to make it mutable and decrement it. Just make the variable binding in the function declaration mut.

5. There's no need to return the unit value (()). Just return will suffice.

6. slice::swap exists. In the broader world, so does mem::swap.

7. With the power of swap, you can remove the need for the Copy bound.

8. Quickcheck is an invaluable tool for problems like this. You can create a property that can be validated across a wide range of automatically generated input.

pub fn insertion_sort<T>(values: &mut [T])
    where T: Ord
{
    for i in 0..values.len() {
        for j in (0..i).rev() {
            if values[j] >= values[j + 1] {
                values.swap(j, j + 1);
            } else {
                break
            }
        }
    }
}

#[macro_use]
extern crate quickcheck;

#[test]
fn test_insertion_sort_empty() {
    let mut values: [i32; 0] = [];
    insertion_sort(&mut values);
    assert_eq!(values, [])
}

#[test]
fn test_insertion_sort_one() {
    let mut values = [1];
    insertion_sort(&mut values);
    assert_eq!(values, [1]);
}

#[test]
fn test_insertion_multi() {
    let mut values = [9, 8, 7, 11, 10];
    insertion_sort(&mut values);
    let values_expected: Vec<_> = (7..12).collect();
    assert_eq!(values_expected, values);
}

quickcheck! {
    fn test_insertion_everything(xs: Vec<i32>) -> bool {
        // Macro doesn't allow `mut` in the `fn` declaration :-(
        let mut xs = xs;

        let mut expected_sorted = xs.clone();
        expected_sorted.sort();

        insertion_sort(&mut xs);

        expected_sorted == xs
    }
}

Answer 2

I also implemented the insertion sort algorithm in Rust, but my version is slightly different than Shepmaster's one. In the following piece of code, which you can also find here, you have a rough comparison, in terms of time performance, between the two versions. Again, you should look at this comparison with a grain of salt. Note: to execute this code, you must specify the crates rand and time as dependencies in your Cargo.toml file.

extern crate rand;
extern crate time;

use rand::Rng;
use time::PreciseTime;

pub fn nbro_insertion_sort<T: Ord>(seq: &mut [T]) {
    for i in 1..seq.len() {
        let mut n = i;
        while n > 0 && seq[n] < seq[n - 1] {
            seq.swap(n, n - 1);
            n = n - 1;
        }
    }
}

pub fn shepmaster_insertion_sort<T>(seq: &mut [T])
where
    T: Ord,
{
    for i in 0..seq.len() {
        for j in (0..i).rev() {
            if seq[j] >= seq[j + 1] {
                seq.swap(j, j + 1);
            } else {
                break;
            }
        }
    }
}

fn new_random_vec(n: usize) -> Vec<i32> {
    let mut rng = rand::thread_rng();
    std::iter::repeat_with(|| rng.gen::<i32>()).take(n).collect()
}

fn main() {
    fn one(name: &str, data: &[i32], f: impl FnOnce(&mut [i32])) { 
        let mut vec = data.to_vec();

        let start = PreciseTime::now();
        f(&mut vec);
        let end = PreciseTime::now();

        println!(
            "{} seconds to sort {} integers, using {}",
            start.to(end),
            data.len(),
            name,
        );

    }

    let base_vec = new_random_vec(10_000);
    one("shepmaster_insertion_sort", &base_vec, shepmaster_insertion_sort);
    one("nbro_insertion_sort", &base_vec, nbro_insertion_sort);
}