How to check if a list is ordered?

Question

I am doing some unit tests and I want to know if there's any way to test if a list is ordered by a property of the objects it contains.

Right now I am doing it this way but I don't like it, I want a better way. Can somebody help me please?

// (fill the list)
List<StudyFeedItem> studyFeeds = 
    Feeds.GetStudyFeeds(2120, DateTime.Today.AddDays(-200), 20);   

StudyFeedItem previous = studyFeeds.First();

foreach (StudyFeedItem item in studyFeeds)
{
    if (item != previous)
    {
        Assert.IsTrue(previous.Date > item.Date);
    }

    previous = item;
}

Pinna

Be careful that you're not testing things that don't need to be tested. Are you ensuring that the query contains the expected order by clause, or are you merely checking to see that the order by clause works? The latter is wasteful. – Ito

@Ito - this is a good point (+1), and I wondered the same thing when I was asking the question. Why would you say that testing the order by is wasteful? Should I then simply trust the DB engine and the CLR to keep things straight? – Thorathoracic

@PITADev: Yes, you should absolutely trust that the DB engine and the CLR keep things straight. You're not testing that int x = 2, y = 2, z = x + y has Assert.IsTrue(z == 4)' succeed are you? You should unit test the behavior of your public methods and nothing more. So if the expected behavior of repository.GetItems(true) returns an ordered list of items, then test that. But don't test that items.OrderBy(x => x, new YourComparer()) does indeed sort the list. However, do unit test that YourComparer does indeed compare correctly. – Upper

are you absolutely certain it will always be ordered either ascending or descending? – Davie

Nope, that's something I want to test in two different scenarios – Tatman

l.OrderBy(e => e).SequenceEqual(l) easiest way with LINQ – Calyces

@Dennis What's wrong with Linq based answers though? I'm missing that. Anyway, I'll close the question. – Obovoid

@SriramSakthivel: nothing wrong (except performance). Just haven't scrolled to non-LINQ ones. – Frontogenesis

@Martin I issued a merge request using a flag. I'd love to write a new community wiki question to provide an even better merge target (i.e. not "too localized" nor "too broad") that all answers can be migrated to. I'm fairly sure there's about a hundred "How to check if a [list|collection|array] is sorted [ascending|descending|either way]" questions, all of them with their own answers repeating the approach shown here. We need more curation of such canconicals. – Harping

@PavelZagalsky Could you please unmark my answer? You can choose either TIm's or Martin's answer. Thanks. – Psf

Sure, I have used your answer anyway because for my use it was sufficient enough. Thanks again – Tatman

Answer 1

If you are using MSTest, you may want to take a look at CollectionAssert.AreEqual.

Enumerable.SequenceEqual may be another useful API to use in an assertion.

In both cases you should prepare a list that holds the expected list in the expected order, and then compare that list to the result.

Here's an example:

var studyFeeds = Feeds.GetStudyFeeds(2120, DateTime.Today.AddDays(-200), 20);   
var expectedList = studyFeeds.OrderByDescending(x => x.Date);
Assert.IsTrue(expectedList.SequenceEqual(studyFeeds));

Sandalwood

The question was: "is there's any way to test if a list is ordered by a property of the objects it contains.", So: a test that returns true if the sequence is ordered by a given property. NOT: if the sequence equals another sequence. I'd go for an extension method, possibly using Enumerable.Aggregate – Poock

Answer 2

A .NET 4.0 way would be to use the Enumerable.Zip method to zip the list with itself offset by one, which pairs each item with the subsequent item in the list. You can then check that the condition holds true for each pair, e.g.

var ordered = studyFeeds.Zip(studyFeeds.Skip(1), (a, b) => new { a, b })
                        .All(p => p.a.Date < p.b.Date);

If you're on an earlier version of the framework you can write your own Zip method without too much trouble, something like the following (argument validation and disposal of the enumerators if applicable is left to the reader):

public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(
    this IEnumerable<TFirst> first,
    IEnumerable<TSecond> second,
    Func<TFirst, TSecond, TResult> selector)
{
    var e1 = first.GetEnumerator();
    var e2 = second.GetEnumerator();
    while (e1.MoveNext() & e2.MoveNext()) // one & is important
        yield return selector(e1.Current, e2.Current);
}

Trejo

This will be more memory efficient than the other answers that use OrderBy(). – Quartet

This needs to be on top. – Evvoia

This can be simplified further so it uses only one lambda expression instead of two and gets rid of the anonymous type, improving readability. See my answer. :) – Lancaster

One thing worth to fix is the condition which should be <= instead. Items with the same date which are next to each other in the collection don't make the order invalid. – Trouveur

Answer 3

Nunit 2.5 introduced CollectionOrderedContraint and a nice syntax for verifying the order of a collection:

Assert.That(collection, Is.Ordered.By("PropertyName"));

No need to manually order and compare.

Chumash

I like this, but at it's current state is very limited (can't order by multiple columns while setting acending/descending. :( – Migratory

The functionality of Nunit has been extended. Assertions now allow the use of your own comparers, as you can see in the manual. Constraints support a number of settings, including the direction and choice of the desired property (multiple properties even). – Cribbage

Answer 4

If your unit testing framework has helper methods to assert equality of collections, you should be able do something like this (NUnit flavored):

var sorted = studyFeeds.OrderBy(s => s.Date);
CollectionAssert.AreEqual(sorted.ToList(), studyFeeds.ToList());

The assert method works with any IEnumerable, but when both collections are of type IList or "array of something", the error message thrown when the assert fails will contain the index of the first out-of-place element.

Patti

+1. Nice. I've used NUnit for years and didn't know about this. Also just discovered FileAssert and StringAssert! Thanks. – Kummerbund

it doesn't work :(. Error message: Baischana.Components.Services.Test.StudyFeedsTest.GetStudyFeeds_IsOrderedByDate: Expected: <System.Linq.OrderedEnumerable`2[Baischana.Components.StudyFeedItem,System.DateTime]> But was: < <Baischana.Components.StudyFeedItem>, <Baischana.Components.StudyFeedItem>, <Baischana.Components.StudyFeedItem>, <Baischana.Components.StudyFeedItem>, <Baischana.Components.StudyFeedItem> > – Pinna

Sorting a list is quite ineffective in terms of computational complexity. – Stimulative

+1 for CollectionAssert, I didn't know that. @el-pescado: that's true, but it's a unit test, not production code... – Terrify

@Nicole: That is the error message you get when the assertion fails. Try to pass the assert method two objects of type IList (my answer is edited to do that), and it should give you another error message, containing the index of the first out-of-place element. – Hombre

Answer 5

The solutions posted involving sorting the list are expensive - determining if a list IS sorted can be done in O(N). Here's an extension method which will check:

public static bool IsOrdered<T>(this IList<T> list, IComparer<T> comparer = null)
{
    if (comparer == null)
    {
        comparer = Comparer<T>.Default;
    }

    if (list.Count > 1)
    {
        for (int i = 1; i < list.Count; i++)
        {
            if (comparer.Compare(list[i - 1], list[i]) > 0)
            {
                return false;
            }
        }
    }
    return true;
}

A corresponding IsOrderedDescending could be implemented easily by changing > 0 to < 0.

Calumnious

>= is wrong, it would return false on [1, 1, 1, 2, 3]. Modifying this to detect a reverse sort is trivial too. – Calumnious

So much better than an approach that sorts the data, (which makes my teeth itch). – Malm

You can't use > or any operator to compare elements inside a generic method. – Obovoid

Works with IList<String> but not with IList<T> or even IEnumerable<T>. – Louiselouisette

Indeed, I should've written that in VS rather than in the browser! Updated with the same comparer method you used. – Calumnious

You don't even need lists or indexed access. You can do it on a simple IEnumerable. – Skylab

Answer 6

Greg Beech answer, although excellent, can be simplified further by performing the test in the Zip itself. So instead of:

var ordered = studyFeeds.Zip(studyFeeds.Skip(1), (a, b) => new { a, b })
                        .All(p => p.a.Date <= p.b.Date);

You can simply do:

var ordered = !studyFeeds.Zip(studyFeeds.Skip(1), (a, b) => a.Date <= b.Date)
                        .Contains(false);

Which saves you one lambda expression and one anonymous type.

(In my opinion removing the anonymous type also makes it easier to read.)

Lancaster

I find this version easier to read : studyFeeds.Zip(studyFeeds.Skip(1), (a, b) => a.Date < b.Date) .All(b => true); – Beachlamar

Personally I can't say I perceive any clarity difference between testing that all is true versus testing if any is false, that extra lambda seems unnecessary to me, but whatever floats your boat I guess. – Lancaster

@Beachlamar I think you've got a typo: (b => true) will always return true ignoring if b is false or true and I think you meant (b => b) – Andersonandert

@SteveCadwallader Yes you're right, can't edit back. Correct form is : studyFeeds.Zip(studyFeeds.Skip(1), (a, b) => a.Date < b.Date) .All(b => b); – Beachlamar

Since it now reads as "All b" instead of "All true" I don't think it's easier to read at all. When you read All(b => b) you pause for a moment thinking about it to realize we are doing an "all true"-test, and then have to re-read the preceding part to see the actual condition we are testing. – Lancaster

One thing worth to fix is the condition which should be <= instead. Same values next to each other doesn't make the order invalid – Trouveur

This is great, and it can go a bit further too: var ordered = !studyFeeds.Zip(studyFeeds.Skip(1), (a, b) => a.Date <= b.Date).Min(); – Wrung

@RyanNaccarato What do you mean? You are doing a Min on an IEnumerable<bool>. – Lancaster

Yep! The min value in a list of bools is false (0), the max being true (1). So, .Min() will do the trick. – Wrung

@RyanNaccarato Aha, well in that case you have a small bug: you need to remove the negation in front of "!studyFeeds..." since you swapped Contains(false) which is true if the list is unordered to Min() which is false if the list is unordered. You saved one more char. ;) ...However I'm not sure if Min over bool is smart enough to stop when it encounters the first false value or not. If it isn't smart enough to do that then the performance has degraded. – Lancaster

Yes, you are correct, no ! needed. – Wrung

Answer 7

if(studyFeeds.Length < 2)
  return;

for(int i = 1; i < studyFeeds.Length;i++)  
 Assert.IsTrue(studyFeeds[i-1].Date > studyFeeds[i].Date);

for isn't dead just quite yet!

Wig

Answer 8

How about:

var list = items.ToList();
for(int i = 1; i < list.Count; i++) {
    Assert.IsTrue(yourComparer.Compare(list[i - 1], list[i]) <= 0);
} 

where yourComparer is an instance of YourComparer which implements IComparer<YourBusinessObject>. This ensures that every element is less than the next element in the enumeration.

Upper

FYI: merged from #1676678 – Ikon

asserting is only good in Debug, it will tell you if the list is order, but wont do anything in a release, Assert is good for verification when something should always be true! – Easley

Answer 9

You could use an extension method like this:

public static System.ComponentModel.ListSortDirection? SortDirection<T>(this IEnumerable<T> items, Comparer<T> comparer = null)
{
    if (items == null) throw new ArgumentNullException("items");
    if (comparer == null) comparer = Comparer<T>.Default;

    bool ascendingOrder = true; bool descendingOrder = true;
    using (var e = items.GetEnumerator())
    {
        if (e.MoveNext())
        {
            T last = e.Current; // first item
            while (e.MoveNext())
            {
                int diff = comparer.Compare(last, e.Current);
                if (diff > 0)
                    ascendingOrder = false;
                else if (diff < 0)
                    descendingOrder = false;

                if (!ascendingOrder && !descendingOrder)
                    break;
                last = e.Current;
            }
        }
    }
    if (ascendingOrder)
        return System.ComponentModel.ListSortDirection.Ascending;
    else if (descendingOrder)
        return System.ComponentModel.ListSortDirection.Descending;
    else
        return null;
}

It enables to check if the sequence is sorted and also determines the direction:

var items = new[] { 3, 2, 1, 1, 0 };
var sort = items.SortDirection();
Console.WriteLine("Is sorted? {0}, Direction: {1}", sort.HasValue, sort);
//Is sorted? True, Direction: Descending

Louiselouisette

This iterates the input a lot more than I'd expect a self-contained LINQ function to. – Kaleb

@Rawling: because of Any and First. That doesn't iterate the sequence but only checks the first. If any of the items is not ordered it will stop enumeration and return false. – Louiselouisette

It still calls GetEnumerable. If that's expensive, and it can be, you're calling it three times more than you need to. – Kaleb

@Rawling: true, and the accepted answer is more elegant. But isn't OrderBy + SequenceEqual less efficient because it needs to order the whole sequence before it can start with SequenceEqual whereas my foreach can compare the order immediately? It also needs to process it twice to check both directions whereas my loop only needs one. – Louiselouisette

@TimSchmelter Your answer is a way better than the accepted. But I would personally use implicit enumerator (using (var e = items.GetEnumerator()) with e.MoveNext() and e.Current) to avoid Any(), 'Skip, and First`. – Attempt

Tim, I agree yours is way better than the accepted, yes :) – Kaleb

@Rawling: I have edited my answer. One question: is an empty collection or one that contains only one item ordered or not? If it is, in which direction? The method above returns Ascending, is that correct? – Louiselouisette

Answer 10

Linq based answer is:

You can use SequenceEqual method to check if the original and ordered one is same or not.

var isOrderedAscending = lJobsList.SequenceEqual(lJobsList.OrderBy(x => x));
var isOrderedDescending = lJobsList.SequenceEqual(lJobsList.OrderByDescending(x => x));

Don't forget to import System.Linq namespace.

Additionally:

I am repeating that this answer is Linq based, you can achieve more efficiency by creating your custom extension method.

Also, if somebody still wants to use Linq and check if the sequence both is ordered in ascending or descending order, then you can achieve a little bit more efficiency like that:

var orderedSequence = lJobsList.OrderBy(x => x)
                               .ToList();

var reversedOrderSequence = orderedSequence.AsEnumerable()
                                           .Reverse();

if (lJobsList.SequenceEqual(orderedSequence))
{
     // Ordered in ascending
}
else (lJobsList.SequenceEqual(reversedOrderSequence))
{
     // Ordered in descending
}

Psf

@PavelZagalsky Glad to help. But don't forget there exist other more efficient approachs which must be implemented by yourself. – Psf

@Harping 1) Don't use such words the most horrible approach!!!. 2) I wrote in my answer that this is not the most efficient. But if the sequences are not big, then this solution may come handy in urgent moments. 3) The answer is right at the end! 4) Also I want to say that, don't think that I don't know to count iterations on my linq code. I know how Linq works. And have read all LINQ extension methods source codes. 5) Have a nice day. – Psf

@Harping "Don't get offended if someone points out a flaw in your code" which I have mentioned already in my answer. It looks like that: You are trying to tell me that pen is a pen. We already know that. – Psf

You mention "Linq based" and "extension method", which have nothing to do with performance. Again, you could do yourself a great benefit by not getting offended so easily. – Harping

@Harping Also, you have wrote that I was complaining. Yes. But my coplaining was about the braveness of the downoter. I was aware of that my answer is not the most efficient. But, the downvoter was not so brave to comment that to my answer. And you are very good to use metaphoric phrases in your sentences. – Psf

@Harping I have copied that from my answer : I am repeating that this answer is Linq based, you can achieve more efficiency by creating your custom extension method.. I mean custom extension method for IEnumerable<T>. – Psf

And I'll repeat, Linq and extension methods have nothing to do with performance. – Harping

@Harping I am speaking about built-in Linq methods! Your custom extension method about some special logic will be mor efficeient than using built-in multiple Linq methods. I am totally sure that, I know how such things work in .Net ;). So, have a nice day. This is my last comment. I will dlete the answer. – Psf

Answer 11

Here's how I do it with Linq and I comparable, might not be the best but works for me and it's test framework independent.

So the call looks like this:

    myList.IsOrderedBy(a => a.StartDate)

This works for anything that implements IComparable, so numbers strings and anything that inherit from IComparable:

    public static bool IsOrderedBy<T, TProperty>(this List<T> list, Expression<Func<T, TProperty>> propertyExpression) where TProperty : IComparable<TProperty>
    {
        var member = (MemberExpression) propertyExpression.Body;
        var propertyInfo = (PropertyInfo) member.Member;
        IComparable<TProperty> previousValue = null;
        for (int i = 0; i < list.Count(); i++)
        {
            var currentValue = (TProperty)propertyInfo.GetValue(list[i], null);
            if (previousValue == null)
            {
                previousValue = currentValue;
                continue;
            }

            if(previousValue.CompareTo(currentValue) > 0) return false;
            previousValue = currentValue;

        }

        return true;
    }

Hope this helps, took me ages to work this one out.

Aleida

Answer 12

Checking a sequence can have four different outcomes. Same means that all elements in the sequence are the same (or the sequence is empty):

enum Sort {
  Unsorted,
  Same,
  SortedAscending,
  SortedDescending
}

Here is a way to check the sorting of a sequence:

Sort GetSort<T>(IEnumerable<T> source, IComparer<T> comparer = null) {
  if (source == null)
    throw new ArgumentNullException(nameof(source));
  if (comparer == null)
    comparer = Comparer<T>.Default;

  using (var enumerator = source.GetEnumerator()) {
    if (!enumerator.MoveNext())
      return Sort.Same;
    Sort? result = null;
    var previousItem = enumerator.Current;
    while (enumerator.MoveNext()) {
      var nextItem = enumerator.Current;
      var comparison = comparer.Compare(previousItem, nextItem);
      if (comparison < 0) {
        if (result == Sort.SortedDescending)
          return Sort.Unsorted;
        result = Sort.SortedAscending;
      }
      else if (comparison > 0) {
        if (result == Sort.SortedAscending)
          return Sort.Unsorted;
        result = Sort.SortedDescending;
      }
    }
    return result ?? Sort.Same;
  }
}

I'm using the enumerator directly instead of a foreach loop because I need to examine the elements of the sequence as pairs. It makes the code more complex but is also more efficient.

Scientism

Answer 13

One way or another you're going to have to walk the list and ensure that the items are in the order you want. Since the item comparison is custom, you could look into creating a generic method for this and passing in a comparison function - the same way that sorting the list uses comparison functions.

Ketonuria

Answer 14

Something LINQ-y would be to use a separate sorted query...

var sorted = from item in items
 orderby item.Priority
 select item;

Assert.IsTrue(items.SequenceEquals(sorted));

Type inference means you'd need a

 where T : IHasPriority

However, if you have multiple items of the same priority, then for a unit test assertion you're probably best off just looping with the list index as Jason suggested.

Washery

FYI: merged from #1676678 – Ikon

Answer 15

var studyFeeds = Feeds.GetStudyFeeds(2120, DateTime.Today.AddDays(-200), 20);
var orderedFeeds = studyFeeds.OrderBy(f => f.Date);

for (int i = 0; i < studyFeeds.Count; i++)
{
    Assert.AreEqual(orderedFeeds[i].Date, studyFeeds[i].Date);
}

Comfort

Answer 16

What about something like this, without sorting the list

    public static bool IsAscendingOrder<T>(this IEnumerable<T> seq) where T : IComparable
    {
        var seqArray = seq as T[] ?? seq.ToArray();
        return !seqArray.Where((e, i) =>
            i < seqArray.Count() - 1 &&
            e.CompareTo(seqArray.ElementAt(i + 1)) >= 0).Any();
    }

Pittel

Answer 17

Here's a more lightweight generic version. To test for descending order, change the >= 0 comparison to <= 0.

public static bool IsAscendingOrder<T>(this IEnumerable<T> seq) where T : IComparable<T>
{
    var predecessor = default(T);
    var hasPredecessor = false;

    foreach(var x in seq)
    {
        if (hasPredecessor && predecessor.CompareTo(x) >= 0) return false;
        predecessor = x;
        hasPredecessor = true;
    }

    return true;
}

Tests:

• new int[] { }.IsAscendingOrder() returns true
• new int[] { 1 }.IsAscendingOrder() returns true
• new int[] { 1,2 }.IsAscendingOrder() returns true
• new int[] { 1,2,0 }.IsAscendingOrder() returns false

Ernestineernesto

Answer 18

While AnorZaken's and Greg Beech's answers are very nice, as they don't require using an extension method, it can be good to avoid Zip() sometimes, as some enumerables can be expensive to enumerate in this way.

A solution can be found in Aggregate()

double[] score1 = new double[] { 12.2, 13.3, 5, 17.2, 2.2, 4.5 };
double[] score2 = new double[] { 2.2, 4.5, 5, 12.2, 13.3, 17.2 };

bool isordered1 = score1.Aggregate(double.MinValue,(accum,elem)=>elem>=accum?elem:double.MaxValue) < double.MaxValue;
bool isordered2 = score2.Aggregate(double.MinValue,(accum,elem)=>elem>=accum?elem:double.MaxValue) < double.MaxValue;

Console.WriteLine ("isordered1 {0}",isordered1);
Console.WriteLine ("isordered2 {0}",isordered2);

One thing a little ugly about the above solution, is the double less-than comparisons. Floating comparisons like this make me queasy as it is almost like a floating point equality comparison. But it seems to work for double here. Integer values would be fine, also. The floating point comparison can be avoided by using nullable types, but then the code becomes a bit harder to read.

double[] score3 = new double[] { 12.2, 13.3, 5, 17.2, 2.2, 4.5 };
double[] score4 = new double[] { 2.2, 4.5, 5, 12.2, 13.3, 17.2 };

bool isordered3 = score3.Aggregate((double?)double.MinValue,(accum,elem)=>(elem>(accum??(double?)double.MaxValue).Value)?(double?)elem:(double?)null) !=null;
bool isordered4 = score4.Aggregate((double?)double.MinValue,(accum,elem)=>(elem>(accum??(double?)double.MaxValue).Value)?(double?)elem:(double?)null) !=null;

Console.WriteLine ("isordered3 {0}",isordered3);
Console.WriteLine ("isordered4 {0}",isordered4);

Aramanta

Answer 19

You can create an ordered and an unordered version of the list first:

var asc = jobs.OrderBy(x => x);
var desc = jobs.OrderByDescending(x => x);

Now compare the original list with both:

if (jobs.SequenceEqual(asc) || jobs.SequenceEquals(desc)) // ...

Piste

Answer 20

You can use lambda in extension:

public static bool IsAscending<T>(this IEnumerable<T> self, Func<T, T, int> compareTo) {
  var list = self as IList<T> ?? self.ToList();
  if (list.Count < 2) {
    return true;
  }
  T a = list[0];
  for (int i = 1; i < list.Count; i++) {
    T b = list[i];
    if (compareTo(a, b) > 0) {
      return false;
    }
    a = b;
  }
  return true;
}

Using:

bool result1 = Enumerable.Range(2, 10).IsAscending((a, b) => a.CompareTo(b));

more:

var lst = new List<(int, string)> { (1, "b"), (2, "a"), (3, "s1"), (3, "s") };
bool result2 = lst.IsAscending((a, b) => {
  var cmp = a.Item1.CompareTo(b.Item1);
  if (cmp != 0) {
    return cmp;
  } else {
    return a.Item2.CompareTo(b.Item2);
  }
});

Magnolia

Answer 21

Microsoft.VisualStudio.TestTools.UnitTesting.CollectionAssert.AreEqual(
  mylist.OrderBy((a) => a.SomeProperty).ToList(),
  mylist,
  "Not sorted.");

Campbellite

Can you explain what your code is doing? Posting just code as an answer is not the best practice. – Tunicle

Answer 22

All of the answers given are based on asserting items are in a given order, rather than a more general test (perhaps to avoid an unnecessary sort).

I use this to check if items are in a given order before committing to sort them:

public static bool All<T>(this IEnumerable<T> values, Func<T, T, bool> function)
{
   if(values == null)
      throw new ArgumentNullException(nameof (values));
   if(function == null)
      throw new ArgumentNullException(nameof (function));
   using(IEnumerator<T> e = values.GetEnumerator())
   {
      if(e.MoveNext())
      {
         T left = e.Current;
         if(!e.MoveNext())
            return true;
         T right = e.Current;
         do
         {
            if(!function(left, right))
               return false;
            left = right;
            right = e.Current;
         }
         while(e.MoveNext());
      }
      return true;
   }
}

public static void AllExample()
{
   int[] items = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

   /// true if the elements appear in ascending order:

   items.All((a, b) => a <= b);
}

Pandora

Answer 23

var expectedList = resultA.ToArray();
var actualList = resultB.ToArray();
var i = 0;
foreach (var item in expectedList)
{
     Assert.True(expectedList[i].id == actualList[i].id);
     i++;
}

Thera

Why are you using a foreach loop if you don't intent to use the iteration variable? That doesn't make sense and you should probably be using a for loop instead. – Atalie