6
\$\begingroup\$

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.

\$\endgroup\$
10
\$\begingroup\$
  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
    }
}
\$\endgroup\$
1
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$ – Toby Speight Nov 7 '18 at 18:21
  • \$\begingroup\$ @TobySpeight This answer is an extension to the Shepmaster's one. So, you should read Shepmaster's one and then mine. \$\endgroup\$ – nbro Nov 7 '18 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.