sorting_algorithms/
lib.rs

1#![warn(clippy::all)]
2
3/// The function implements the optimized bubble sort.
4/// It sorts the element in the input slice by mutating it.
5///
6/// This is a exact implementation of the pseudo code from
7/// [Wikipedia](https://en.wikipedia.org/wiki/Bubble_sort):
8///
9/// ```text
10/// procedure bubbleSort(A : list of sortable items)
11///     n := length(A)
12///     repeat
13///         newn := 0
14///         for i := 1 to n - 1 inclusive do
15///             if A[i - 1] > A[i] then
16///                 swap(A[i - 1], A[i])
17///                 newn := i
18///             end if
19///         end for
20///         n := newn
21///     until n ≤ 1
22/// end procedure
23/// ```
24///
25/// # Arguments
26///
27/// * list - The list to be sorted
28///
29/// # Examples
30///
31/// ```
32/// use bubble_sort::bubble_sort;
33///
34/// let mut list = [ 2, 3, 5, 4, 1 ];
35/// bubble_sort(&mut list);
36/// assert_eq!(list, [ 1, 2, 3, 4, 5 ]);
37/// ```
38///
39pub fn bubble_sort<T: PartialOrd>(list: &mut[T]) {
40    let mut n = list.len();
41    loop {
42        let mut lastly_swapped= 0;
43        for i in 1..n {
44            if list[i - 1] > list[i] {
45                list.swap(i - 1, i);
46                lastly_swapped = i;
47            }
48        }
49        n = lastly_swapped;
50        if n <= 1 {
51            break;
52        }
53    }
54}
55
56#[cfg(test)]
57mod tests {
58    #[test]
59    fn test_bubble_sort() {
60        use super::bubble_sort;
61
62        let mut list = [4, 8, 9, 2, 3];
63        bubble_sort(&mut list);
64        assert_eq!(list, [2, 3, 4, 8, 9]);
65    }
66
67    #[test]
68    fn test_bubble_sort_with_ordered_array() {
69        use super::bubble_sort;
70
71        let mut list = [2, 3, 4, 8, 9];
72        bubble_sort(&mut list);
73        assert_eq!(list, [2, 3, 4, 8, 9]);
74    }
75
76    #[test]
77    fn test_bubble_sort_with_reverse_ordered_array() {
78        use super::bubble_sort;
79
80        let mut list = [9, 8, 4, 3, 2];
81        bubble_sort(&mut list);
82        assert_eq!(list, [2, 3, 4, 8, 9]);
83    }
84
85    #[test]
86    fn test_bubble_sort_with_single_element_array() {
87        use super::bubble_sort;
88
89        let mut list= [ 42 ];
90        bubble_sort(&mut list);
91        assert_eq!(list, [ 42 ]);
92    }
93
94    #[test]
95    fn test_bubble_sort_with_empty_array() {
96        use super::bubble_sort;
97
98        let mut list: [usize; 0] = [];
99        bubble_sort(&mut list);
100        assert_eq!(list, []);
101    }
102
103    #[test]
104    fn test_bubble_sort_with_vec() {
105        use super::bubble_sort;
106
107        let mut list = vec![4, 8, 9, 2, 3];
108        bubble_sort(&mut list);
109        assert_eq!(list, [2, 3, 4, 8, 9]);
110    }
111}
sorting_algorithms/lib.rs

sorting_algorithms/
lib.rs
