algorithms_rs/sort/
select_sort.rs1use super::Sort;
2
3#[derive(Debug)]
5pub struct SelectSort<T> {
6 arr: Vec<T>,
7}
8
9impl<T> From<Vec<T>> for SelectSort<T> {
10 fn from(arr: Vec<T>) -> Self {
11 Self { arr }
12 }
13}
14
15impl<T: core::clone::Clone> From<&[T]> for SelectSort<T> {
16 fn from(arr: &[T]) -> Self {
17 Self { arr: arr.into() }
18 }
19}
20
21impl<T> SelectSort<T> {
22 pub fn select_sort<F>(&mut self, f: F)
23 where
24 F: FnOnce(&T, &T) -> bool + core::marker::Copy,
25 {
26 for i in 0..self.arr.len() {
27 let mut min = i; for j in (i + 1)..self.arr.len() {
30 if f(&self.arr[j], &self.arr[min]) {
31 min = j;
32 }
33 }
34 self.arr.swap(i, min);
35 }
36 }
37
38 pub fn select_sort_by_find_smallest<F>(&mut self, f: F) -> Vec<T>
39 where
40 F: FnOnce(Option<&T>, Option<&T>) -> bool + core::marker::Copy,
41 {
42 let mut result = vec![];
43 for _ in 0..self.arr.len() {
44 let smallest = self.find_smallest(f);
45 result.push(self.arr.swap_remove(smallest));
46 }
47 result
48 }
49
50 pub fn find_smallest<F>(&self, f: F) -> usize
51 where
52 F: FnOnce(Option<&T>, Option<&T>) -> bool + core::marker::Copy,
53 {
54 let mut smallest = self.arr.get(0);
55 let mut smallest_index = 0usize;
56 for i in 1..self.arr.len() {
57 if f(self.arr.get(i), smallest) {
58 smallest = self.arr.get(i);
59 smallest_index = i;
60 }
61 }
62 smallest_index
63 }
64}
65
66impl<T: core::cmp::PartialOrd + Clone> Sort<T> for SelectSort<T> {
67 fn inner(&self) -> Vec<T> {
68 self.arr.clone()
69 }
70
71 fn sort_by<F>(&mut self, f: F)
72 where
73 F: FnOnce(&T, &T) -> bool + core::marker::Copy,
74 {
75 self.select_sort(f)
76 }
77}
78
79#[cfg(test)]
80mod tests {
81 use super::*;
82
83 #[test]
84 fn test_select_sort_ok() {
85 let mut select = SelectSort::from(vec![10, 9, 8, 6, 5, 4, 3, 2, 1]);
86 select.sort();
87 assert!(select.is_sort());
88 }
89
90 #[test]
91 fn test_select_sort_a_empty_arr() {
92 let mut select = SelectSort::from(Vec::<i32>::new());
93 select.sort();
94 assert!(select.is_sort());
95 }
96
97 #[test]
98 fn test_select_sort_by_find_smallest() {
99 let mut select = SelectSort::from(vec![10, 9, 8, 6, 5, 4, 3, 2, 1]);
100 let result = select.select_sort_by_find_smallest(|v1, v2| v1 < v2);
101 assert_eq!(result, vec![1, 2, 3, 4, 5, 6, 8, 9, 10]);
102 }
103}