rost 0.2.1

A library for sorting
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
93
94
95
96
97
98
99
100

//! # Rost
//!
//! A library for rosting. --- Ahem, I meant sorting.
//!
//! This crate is inspired by <https://github.com/FedericoStra/Sorting>.

/// An algorithm for sorting.
///
/// This trait identifies algorithms suitable for sorting slices.
pub trait SortingAlgorithm {
    /// Sorts the given slice.
    fn sort<T: Ord>(&self, slice: &mut [T]);
}

/// <https://github.com/orlp/pdqsort>
pub struct PDQsort;

impl SortingAlgorithm for PDQsort {
    fn sort<T: Ord>(&self, slice: &mut [T]) {
        slice.sort_unstable();
    }
}

/// <https://en.wikipedia.org/wiki/Timsort>
pub struct Timsort;

impl SortingAlgorithm for Timsort {
    fn sort<T: Ord>(&self, slice: &mut [T]) {
        slice.sort();
    }
}

/// <https://en.wikipedia.org/wiki/Insertion_sort>
pub struct InsertionSort;

impl SortingAlgorithm for InsertionSort {
    fn sort<T: Ord>(&self, slice: &mut [T]) {
        for i in 1..slice.len() {
            let mut j = i;
            while j > 0 && slice[j - 1] > slice[j] {
                slice.swap(j - 1, j);
                j -= 1;
            }
        }
    }
}

/// Sorts the given slice using a specific [`SortingAlgorithm`].
pub fn sort<T: Ord, A: SortingAlgorithm>(slice: &mut [T], algo: &A) {
    algo.sort(slice);
}

/// Checks if the elements of the slice are sorted.
///
/// That is, for each element `a` and its following element `b`, `a <= b` must hold. If the
/// slice contains exactly zero or one element, `true` is returned.
///
/// Note that if `T` is only `PartialOrd`, but not `Ord`, the above definition implies
/// that this function returns `false` if any two consecutive items are not comparable.
pub fn is_sorted<T: PartialOrd>(slice: &[T]) -> bool {
    for i in 1..slice.len() {
        if let Some(std::cmp::Ordering::Greater) | None = slice[i - 1].partial_cmp(&slice[i]) {
            return false;
        }
    }
    true
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn timsort() {
        let mut v = [1, 2, 3, 6, 3, 1, 3, -4, 6, -2, 3, 0, 5, 3, 0, 12];
        Timsort.sort(&mut v);
        assert!(is_sorted(&v));
    }

    #[test]
    fn pdqsort() {
        let mut v = [1, 2, 3, 6, 3, 1, 3, -4, 6, -2, 3, 0, 5, 3, 0, 12];
        PDQsort.sort(&mut v);
        assert!(is_sorted(&v));
    }

    #[test]
    fn insertion_sort() {
        let mut v = [1, 2, 3, 6, 3, 1, 3, -4, 6, -2, 3, 0, 5, 3, 0, 12];
        InsertionSort.sort(&mut v);
        assert!(is_sorted(&v));
    }

    #[test]
    fn it_sorts() {
        let mut v = [1, 2, 3, 6, 3, 1, 3, -4, 6, -2, 3, 0, 5, 3, 0, 12];
        sort(&mut v, &Timsort);
        assert!(is_sorted(&v));
    }
}