algorithms_rs/sort/
bubble_sort.rs

1// Sort the array using bubble sort. The idea behind
2// bubble sort is to look for adjacent indexes which
3// are out of place and interchange their elements
4// until the entire array is sorted.
5use super::Sort;
6
7/// bubble sort
8#[derive(Debug)]
9pub struct BubbleSort<T> {
10    arr: Vec<T>,
11}
12
13impl<T> From<Vec<T>> for BubbleSort<T> {
14    fn from(arr: Vec<T>) -> Self {
15        Self { arr }
16    }
17}
18
19impl<T: core::clone::Clone> From<&[T]> for BubbleSort<T> {
20    fn from(arr: &[T]) -> Self {
21        Self { arr: arr.into() }
22    }
23}
24
25impl<T: Clone + core::cmp::PartialOrd> Sort<T> for BubbleSort<T> {
26    fn inner(&self) -> Vec<T> {
27        self.arr.clone()
28    }
29
30    fn sort_by<F>(&mut self, f: F)
31    where
32        F: FnOnce(&T, &T) -> bool + core::marker::Copy,
33    {
34        let _ = self.bubble_sort_by(f);
35    }
36}
37
38impl<T: core::cmp::PartialOrd> BubbleSort<T> {
39    /// bubble sort can customize the comparison logic based on the comparison function passed in
40    pub fn bubble_sort_by<F>(&mut self, cmp_fun: F) -> bool
41    where
42        F: FnOnce(&T, &T) -> bool + core::marker::Copy,
43    {
44        if self.arr.is_empty() {
45            return true;
46        }
47
48        let mut sorted = false;
49        let len = self.arr.len();
50
51        while !sorted {
52            sorted = true;
53            (0..(len - 1)).for_each(|idx| {
54                if cmp_fun(&self.arr[idx + 1], &self.arr[idx]) {
55                    self.arr.swap(idx, idx + 1);
56                    sorted = false;
57                }
58            })
59        }
60
61        sorted
62    }
63}
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_bubble_sort() {
71        let mut bubble = BubbleSort::from(vec![10, 4, 6, 8, 13, 2, 3]);
72        bubble.sort();
73        println!("{bubble:?}");
74        assert!(bubble.is_sort());
75    }
76
77    #[test]
78    fn test_bubble_sort_a_empty_arr() {
79        let mut bubble = BubbleSort::from(Vec::<i32>::new());
80        bubble.sort();
81        assert!(bubble.is_sort());
82    }
83}