19
\$\begingroup\$

For a WPF application, I have to sort the items in ObservableCollection after Added new item.

public void UpdateSource(ObservableCollection<SomeType> source, SomeType newItem)
{
    source.Add(newItem);
    SortSource(source, newItem);
}

private void SortSource(ObservableCollection<SomeType> source, SomeType item)
{
    var oldIndex = source.IndexOf(item);
    var list = source.OrderBy(_=>_.SomeProperty).ToList();
    var newIndex = list.IndexOf(item);

    source.Move(oldIndex, newIndex);
}

In order to keep the observable functionality for binding element, the ObservableCollection reference cannot be changed, so I used an assistance list to help me sort the souce.

Any improvement about this?

\$\endgroup\$

1 Answer 1

31
\$\begingroup\$

Your code unnecessarily sorts the whole collection on each insert (which is likely going to be O(n log n)). It also produces two events for each insert (one for Add and one for Move), which also isn't necessary.

What I would do:

  1. Find the index where the inserted item belongs.
  2. Insert the item at that index.

A simple implementation for that could look like this:

public static void AddSorted<T>(this IList<T> list, T item, IComparer<T> comparer = null)
{
    if (comparer == null)
        comparer = Comparer<T>.Default;

    int i = 0;
    while (i < list.Count && comparer.Compare(list[i], item) < 0)
        i++;

    list.Insert(i, item);
}

This could be made faster by using binary search to find the index. Though the total complexity is still going to be O(n), even with binary search, because Insert is O(n) (it has to move all items after the inserted item).

This means that using binary search would help the most if you're often inserting items at or near the end of the collection.


Other notes about your code:

public void UpdateSource(ObservableCollection<SomeType> source, SomeType newItem)

I don't think Update is the right name here, this is not a general update, something like AddToSource would be better.

source.OrderBy(_=>_.SomeProperty)

_ as a parameter name of a lambda is commonly used when you don't care about the value of that parameter. If you do care about it (like here), use something like x, or, even better, a meaningful name.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.