algorithms_rs/sort/
insert_sort.rs1use super::Sort;
2
3#[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 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}