How to check if a IEnumerable is sorted?

Question

bool IsSorted<T>(IEnumerable<T> enumerable)
{
   ???
}

Only by enumerating it and ensure all items are in order. For that T should implement IComparable. — Evk, May 25 '16 at 15:44
a) Define what you mean by sorted. b) Starting with the first item, check if it is sorted with respect to the next item - if it is, check the next item versus the *n+1* item. Continue until you either find a pair out of order (return false) or reach the end (return true) — Matt Burland, May 25 '16 at 15:47
Have you tried anything yet? It's not clear where you are stuck here. — Krease, May 25 '16 at 15:52

score 1 · Accepted Answer · answered May 25 '16 at 15:51

One example of such method could be:

static bool IsSorted<T>(IEnumerable<T> enumerable) where T : IComparable<T> {
    T prev = default(T);
    bool prevSet = false;
    foreach (var item in enumerable) {
        if (prevSet && (prev == null || prev.CompareTo(item) > 0))
            return false;
        prev = item;
        prevSet = true;
    }
    return true;
}

Works with most built-in types like numbers or strings, because they implement IComparable.

Dmitry Bychenko · Answer 2 · 2016-05-25T16:07:25.843

1

Just check that every item is not less then prior one:

  public static partial class EnumerableExtensions {
    public static bool IsSorted<T>(this IEnumerable<T> source, 
                                   IComparer<T> comparer = null) {
      if (null == source)
        throw new ArgumentNullException("source");

      if (null == comparer)
        comparer = Comparer<T>.Default;

      if (null == comparer)
        throw new ArgumentException("No default comparer found.");

      T prior = default(T);
      bool first = true;

      foreach (var item in source) {
        if (!first && comparer.Compare(prior, item) > 0)
          return false;

        first = false;
        prior = item; 
      }

      return true;
    }
  }

edited May 25 '16 at 16:07

answered May 25 '16 at 16:00

Dmitry Bychenko

180,369
20
160
215

2

You don't need to restrict T to be IComparable in your implementation. – Evk May 25 '16 at 16:02
1

@Evk: yes, you can provide a `comparer`; and in case of `IComparable` the `Comparer.Default` can be used – Dmitry Bychenko May 25 '16 at 16:02
1

I just mean "where T: IComparable" is not required for the code to compile. However maybe good to have it still so that caller cannot pass whatever there. – Evk May 25 '16 at 16:05
1

@Evk: I see, finally ;) I should have dropped `where T:...` – Dmitry Bychenko May 25 '16 at 16:08

bgura · Answer 3 · 2016-05-25T20:48:13.330

This checks for Ascending or Descending sort rather than just ascending

   enum SortOrder
    {
        Unknown = 0,
        Ascending = 1,
        Descending = 2
    }

    static bool IsSorted<T>(IEnumerable<T> enumerable)
    {
        var enumerator = enumerable.GetEnumerator();
        // Empty Enumerable
        if (!enumerator.MoveNext())
            return true;
        SortOrder order = SortOrder.None;

        // First Item
        var last = enumerator.Current;
        while(enumerator.MoveNext())
        { 
            var result = Comparer<T>.Default.Compare(last, enumerator.Current);

            switch (order)
            {
                case SortOrder.Unknown:

                    if (result == 0)
                        break;
                    if(result == -1)
                        order = SortOrder.Ascending;
                    else 
                        order = SortOrder.Descending;

                    break;
                case SortOrder.Descending:
                    if (result == -1)
                        return false;
                    break;
                case SortOrder.Ascending:
                    if (result == 1)
                        return false;
                    break;
            }
            last = enumerator.Current;

        }


        return true;
    }

How to check if a IEnumerable is sorted?

3 Answers3

Linked