algorithms_rs/sort/
insert_sort.rs

1use super::Sort;
2
3/// Insert sort
4#[derive(Debug)]
5pub struct InsertSort<T> {
6    arr: Vec<T>,
7}
8
9impl<T> InsertSort<T> {
10    fn insert_sort<F>(&mut self, f: F)
11    where
12        F: FnOnce(&T, &T) -> bool + core::marker::Copy,
13    {
14        let len = self.arr.len();
15
16        for i in 1..len {
17            // do a[i] insert to a[i - 1], a[i - 2], a[i - 3]... among
18            let mut j = i;
19            while j > 0 && f(&self.arr[j], &self.arr[j - 1]) {
20                self.arr.swap(j, j - 1);
21                j -= 1;
22            }
23        }
24    }
25}
26impl<T> From<Vec<T>> for InsertSort<T> {
27    fn from(arr: Vec<T>) -> Self {
28        Self { arr }
29    }
30}
31
32impl<T: core::clone::Clone> From<&[T]> for InsertSort<T> {
33    fn from(arr: &[T]) -> Self {
34        Self { arr: arr.into() }
35    }
36}
37
38impl<T: core::cmp::PartialOrd + Clone> Sort<T> for InsertSort<T> {
39    fn inner(&self) -> Vec<T> {
40        self.arr.clone()
41    }
42
43    fn sort_by<F>(&mut self, f: F)
44    where
45        F: FnOnce(&T, &T) -> bool + core::marker::Copy,
46    {
47        self.insert_sort(f)
48    }
49}
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_insert_sort_ok() {
57        let mut insert = InsertSort::from(vec![10, 9, 8, 6, 5, 4, 3, 2, 1]);
58        println!("insert sort before: {insert:?}");
59        insert.sort();
60        println!("insert sort after: {insert:?}");
61        assert!(insert.is_sort());
62    }
63
64    #[test]
65    fn test_insert_sort_a_empty_arr() {
66        let mut insert = InsertSort::from(Vec::<i32>::new());
67        insert.sort();
68        assert!(insert.is_sort());
69    }
70}
algorithms_rs/sort/insert_sort.rs

algorithms_rs/sort/
insert_sort.rs
