How do I check if a slice is sorted?

Question

How do I check if a slice is sorted?

Assuming a function that accepts a slice of i32, is there an idiomatic Rust way of checking if the slice is sorted?

fn is_sorted(data: &[i32]) -> bool {
    // ...
}

Would it be possible to generalize the above method so that it would accept an iterator?

fn is_sorted<I>(iter: I)
where 
    I: Iterator, 
    I::Item: Ord,
{
    // ...
}

Answer 1

I'd grab pairs of elements and assert they are all in ascending (or descending, depending on what you mean by "sorted") order:

fn is_sorted<T>(data: &[T]) -> bool
where
    T: Ord,
{
    data.windows(2).all(|w| w[0] <= w[1])
}

fn main() {
    assert!(is_sorted::<u8>(&[]));
    assert!(is_sorted(&[1]));
    assert!(is_sorted(&[1, 2, 3]));
    assert!(is_sorted(&[1, 1, 1]));
    assert!(!is_sorted(&[1, 3, 2]));
    assert!(!is_sorted(&[3, 2, 1]));
}

Ditto for generic iterators:

extern crate itertools; // 0.7.8

use itertools::Itertools;

fn is_sorted<I>(data: I) -> bool
where
    I: IntoIterator,
    I::Item: Ord + Clone,
{
    data.into_iter().tuple_windows().all(|(a, b)| a <= b)
}

fn main() {
    assert!(is_sorted(&[] as &[u8]));
    assert!(is_sorted(&[1]));
    assert!(is_sorted(&[1, 2, 3]));
    assert!(is_sorted(&[1, 1, 1]));
    assert!(!is_sorted(&[1, 3, 2]));
    assert!(!is_sorted(&[3, 2, 1]));
}

See also:

• Are there equivalents to slice::chunks/windows for iterators to loop over pairs, triplets etc?

In nightly Rust, there are unstable methods to accomplish this:

• slice::is_sorted
• slice::is_sorted_by
• slice::is_sorted_by_key
• Iterator::is_sorted
• Iterator::is_sorted_by
• Iterator::is_sorted_by_key