Friday, March 19, 2010

How to sort an ObservableCollection

ObservableCollection<T> is frequently used in Silverlight and WPF applications as a bindable data source to elements like ListBoxes and TreeViews.  This is because the collection supports INotifyPropertyChanged, an interface that is referenced by hosts elements so they can be notified whenever the collection changes.

Unlike List<T> and other collection types, ObservableCollection<T> does not natively support sorting.  This post will explore three options for sorting an ObservableCollection.

To start, let’s define Person, a class that supports IComparable, an interface that instructs other objects how to rank person objects.

public class Person : IComparable {
    public string FirstName { get; set; }
    public string LastName { get; set; }
    public int CompareTo(object obj) {
        Person person = obj as Person;
        if (person == null) {
            throw new ArgumentException("Object is not Preson");
        }
        return this.LastName.CompareTo(person.LastName);
    }
}

Next, create a collection of Persons using ObservableCollection<Person> and populate with some well known physicists.

// Create a list of people
ObservableCollection<Person> people = new ObservableCollection<Person>();
people.Add(new Person() { FirstName = "Albert", LastName = "Einsten" });
people.Add(new Person() { FirstName = "Isaac", LastName = "Newton" });
people.Add(new Person() { FirstName = "Niels", LastName = "Bohr" });
people.Add(new Person() { FirstName = "Gottfried", LastName = "Leibniz" });
people.Add(new Person() { FirstName = "Marie", LastName = "Curry" });

The first techniques uses the OrderBy LINQ extension with a simple lambda expression.

ObservableCollection<Person> peopleSort = new ObservableCollection<Person>(
    people.OrderBy(person => person)
);

The disadvantage of this method is that a new collection is created.  Transferring items from the sorted collection to the original collection could be expensive.  The advantage however is that lambda expressions provide almost unlimited flexibility with respect to defining the sorting logic.  By default, Person objects are sorted by the LastName property as defined in its implementation of IComparable.  However to sort by FirstName we can use the following:

ObservableCollection<Person> peopleSort = new ObservableCollection<Person>(
    people.OrderBy(person => person.FirstName)
);

A second method of sorting is to make use of the existing Sort method in List<T>.

List<Person> list = new List<Person>(people);
list.Sort();

But once again, to use this method the end result is the creation of two collections.

Lastly, I would like to describe a third option for sorting ObservableCollection<T> that makes use of the custom LINQ extension as defined below.  The expression performs a bubble sort with the assumption that the items in the generic collection support IComparable.

public static class ListExtension {
    public static void BubbleSort(this IList o) {
        for (int i = o.Count - 1; i >= 0; i--) {
            for (int j = 1; j <= i; j++) {
                object o1 = o[j - 1];
                object o2 = o[j];
                if (((IComparable)o1).CompareTo(o2) > 0) {
                    o.Remove(o1);
                    o.Insert(j, o1);
                }
            }
        }
    }
}

To sort ObservableCollection<Persons> we just need the following statement.

people.BubbleSort();

In summary, I have described three methods of sorting a ObservableCollection<T>.  The first used a List<T>, the second the OrderBy LINQ extension and the last method defined a custom bubble sort LINQ extension.  Each method has its advantages and disadvantages and I am sure are more methods too.  Please feel free to comment if you would like to suggest additional methods.

15 comments:

  1. Thanks, very useful.... All 3 methods are quiet simply described.... thanks a lot!!!!

    ReplyDelete
  2. I prefer using lambdas, so modified your code to fit:

    public static void Sort<TSource, TValue>(this IList<TSource> source, Func<TSource, TValue> selector)
    {
    for (int i = source.Count - 1; i >= 0; i--)
    {
    for (int j = 1; j <= i; j++)
    {
    TSource o1 = source.ElementAt(j - 1);
    TSource o2 = source.ElementAt(j);
    TValue x = selector(o1);
    TValue y = selector(o2);
    var comparer = Comparer<TValue>.Default;
    if (comparer.Compare(x, y) > 0)
    {
    source.Remove(o1);
    source.Insert(j, o1);
    }
    }
    }
    }

    ReplyDelete
  3. @Ian: Thanks for your feedback. Using a lambda expression in the sort LINQ extension is very useful for irregular sorting logic. Thanks again!

    ReplyDelete
  4. If you change the lambda to target only ObservableCollection you can use the 'Move' method provided instead of removing and inserting... although thats probably what it does internally anyway.. just thought I'd throw my two cents in =)

    ReplyDelete
  5. Thank you very much for the Bubble Sort solution, It helped me a lot.

    Pimenta

    ReplyDelete
  6. Thank you, is nice idea, even I like Ian's bit more.
    But please don't change to Move - just noticed, it's not available in WP7.

    ReplyDelete
  7. @cloudy69. Thanks for the tip!
    @pimenta & @anonymous. Thanks for the feedback!

    ReplyDelete
  8. Very nice idea, thanks

    ReplyDelete
  9. Nice simple examples; well done! The last example (bubble sort) can be optimized by setting a Boolean value, 'sorted', to true before the inner loop, and setting it to false when elements are swapped.

    Then exit the algorithm if the inner loop completes and 'sorted' is still true, since this indicates the list is sorted.

    ReplyDelete
  10. You have IList o. Running o.Remove(smth) takes O(n) time. Since the complexity of buble sort is O(n^2) (you have 2 nested loops), your sort implementation takes O(n^3). That's bad.

    But things don't stop here. If you actually sort an ObservableColletion this way, every o.Remove(...) and o.Insert(...) will fire INotifyCollectionChanged. If that collection is databound, that leads to a lot of overhead.

    I guess it's better to make a copy, sort it with O(n*log n) and recreate the ObservableColletion.

    ReplyDelete
  11. Who is Marie Curry :D

    ReplyDelete
    Replies
    1. Oops. Yes, the name should be Marie Curie, no disrespect intended.
      http://www.nobelprize.org/nobel_prizes/physics/laureates/1903/marie-curie-bio.html

      Delete
  12. Another option:
    data = new ObservableCollection();
    view = new CollectionViewSource();
    ...
    view.Source = data;
    view.View.SortDescriptions.Add(new SortDescription("Entfernung", ListSortDirection.Descending));
    myListBox.ItemsSource = view.View;

    ReplyDelete