How do I check if a slice is sorted?

Question

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,
{
    // ...
}

Test that every subsequent element consistently more or less than the previous? — tadman, Jul 10 '18 at 19:17
For record, there is currently an RFC for adding `is_sorted` to the standard library https://github.com/rust-lang/rfcs/pull/2351. — kennytm, Jul 10 '18 at 19:55

Shepmaster · Accepted Answer · 2020-04-13T20:30:53.470

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:

@PeterHall I dunno; usually either you keep a collection sorted by construction (e.g. always adding new values in the "right" place) or by some type invariant (e.g. `BTreeSet`). Have *you* ever wanted to check if something is sorted? :-D Besides, then you have to deal with *which* "sorted" do you mean, and then sorted by a key, etc. — Shepmaster, Jul 10 '18 at 19:46
@Shepmaster "*Have you ever wanted to check if something is sorted?*" -- Quite often, actually: **unit tests and pre/post-condition checks**. [I've written a few more words about this here](https://github.com/LukasKalbertodt/rfcs/blob/rfc-add-is-sorted/text/0000-is-sorted.md#motivation) ;-) — Lukas Kalbertodt, Jul 10 '18 at 20:56
I find it quite noticeable, that this requires a (total) order, rather than a partial order. Never thought about this. — hellow, Jul 11 '18 at 06:32

score 5 · Answer 2 · answered Jul 10 '18 at 22:45

It is not necessary to have Clone for an iterator is_sorted implementation. Here is a no-dependency Rust implementation of is_sorted:

fn is_sorted<I>(data: I) -> bool
where
    I: IntoIterator,
    I::Item: Ord,
{
    let mut it = data.into_iter();
    match it.next() {
        None => true,
        Some(first) => it.scan(first, |state, next| {
            let cmp = *state <= next;
            *state = next;
            Some(cmp)
        }).all(|b| b),
    }
}

Stargateur · Answer 3 · 2023-03-16T17:17:41.193

1

One more using try_fold():

pub fn is_sorted<T: IntoIterator>(t: T) -> bool
where
    <T as IntoIterator>::Item: std::cmp::PartialOrd,
{
    let mut iter = t.into_iter();

    if let Some(first) = iter.next() {
        iter.try_fold(first, |previous, current| {
            (previous > current).then_some(current)
        })
        .is_some()
    } else {
        true
    }
}

edited Mar 16 '23 at 17:17

answered Dec 19 '21 at 18:44

Stargateur

24,473
8
65
91

1

Since the addition of `bool::then_some` the inner could be changed to `(previous <= current).then_some(current)`, using `.is_some()` on the result: `iter.next().map(|first| iter.try_fold(first, |previous, current| (previous <= current).then_some(previous)).is_some()).unwrap_or(true)` – Roland Fredenhagen Mar 16 '23 at 12:46

How do I check if a slice is sorted?

3 Answers3