algori 0.13.0

Rust Algorithms
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

#[cfg(not(feature = "no_std"))]
fn merge<T: Clone>(array: &mut [T], mid: usize, comparator: fn(&T, &T) -> bool) {
    let left = array[..mid].to_vec();
    let right = array[mid..].to_vec();
    let mut left_index = 0;
    let mut right_index = 0;
    let mut index = 0;

    while left_index < left.len() && right_index < right.len() {
        if comparator(&left[left_index], &right[right_index]) {
            array[index] = left[left_index].clone();
            left_index += 1;
        } else {
            array[index] = right[right_index].clone();
            right_index += 1;
        }
        index += 1;
    }

    while left_index < left.len() {
        array[index] = left[left_index].clone();
        left_index += 1;
        index += 1;
    }

    while right_index < right.len() {
        array[index] = right[right_index].clone();
        right_index += 1;
        index += 1;
    }
}
/// Merge Sort
/// # Example
/// ```
/// use algori::sorting::{merge_sort,is_sorted};
/// let mut a = [2,3,1,34,15,8,0,7,4,3,21,4,6,7,4,2341,321,41231,312,62];
/// merge_sort(&mut a ,|a,b| a<=b);
/// assert_eq!(is_sorted(&mut a ,|a,b| a<=b),true);
/// ```
#[cfg(not(feature = "no_std"))]
pub fn merge_sort<T: Clone>(array: &mut [T], comparator: fn(&T, &T) -> bool) {
    if array.len() > 1 {
        if array.len() > 1 {
            let mid = array.len() / 2;
            merge_sort(&mut array[..mid], comparator);
            merge_sort(&mut array[mid..], comparator);
            merge(array, mid, comparator);
        }
    }
}
#[cfg(not(feature = "no_std"))]
#[cfg(test)]
mod tests {
    use super::super::is_sorted;
    use super::*;
    #[test]
    fn test_merge_sort() {
        let mut a = [
            2, 3, 1, 34, 15, 8, 0, 7, 4, 3, 21, 4, 6, 7, 4, 2341, 321, 41231, 312, 62,
        ];
        merge_sort(&mut a, |a, b| a <= b);
        assert!(is_sorted(&a, |a, b| a <= b));
    }

    #[test]
    fn test_merge_sort_empty() {
        let mut a: [i32; 0] = [];
        merge_sort(&mut a, |a, b| a <= b);
        assert!(is_sorted(&a, |a, b| a <= b));
    }

    #[test]
    fn test_merge_sort_single_element() {
        let mut a = [1];
        merge_sort(&mut a, |a, b| a <= b);
        assert!(is_sorted(&a, |a, b| a <= b));
    }

    #[test]
    fn test_merge_sort_already_sorted() {
        let mut a = [1, 2, 3, 4, 5];
        merge_sort(&mut a, |a, b| a <= b);
        assert!(is_sorted(&a, |a, b| a <= b));
    }

    #[test]
    fn test_merge_sort_reverse_sorted() {
        let mut a = [5, 4, 3, 2, 1];
        merge_sort(&mut a, |a, b| a <= b);
        assert!(is_sorted(&a, |a, b| a <= b));
    }
}