sort_algorithms/sort/
insertion_sort.rs

1#[cfg(test)]
2mod insertion_sort_test {
3
4    #[test]
5    fn sort() {
6        let mut arr = vec![7, 6, 5, 2, 4, 3, 1, 0, -1];
7        super::insertion_sort(&mut arr, |a, b| a < b);
8        assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6, 7]);
9    }
10}
11
12/**
13Insertion sort is an algorithm that use strategy where catch one element and compare against orthers.
14# Examples
15
16```
17extern crate sort_algorithms;
18use sort_algorithms::insertion_sort;
19
20let mut arr = vec![7, 6, 5, 2, 4, 3, 1, 0];
21insertion_sort(&mut arr, |a, b| a < b);
22assert_eq!(arr, [0, 1, 2, 3, 4, 5, 6, 7]);
23```
24*/
25
26pub fn insertion_sort<T>(arr: &mut [T], compare: fn(&T, &T) -> bool) {
27    for i in 1..arr.len() {
28        let mut j = i;
29        while j > 0 && compare(&arr[j], &arr[j - 1]) {
30            arr.swap(j, j - 1);
31            j -= 1;
32        }
33    }
34}