CODEWITHSUNDEEP
c#linqcollections
Jasmeet
Jasmeet

Reputation: 1460

Fastest way to insert a value in int List and then sort the list

I am working with dynamic int generic List. I am trying to add and then sort the list in descending order. This operation occurs number of timmes. Currently I am using Linq to do this as.

list.Add(b);
list = list.OrderByDescending(i => i).ToList();

Is there some way to improve the performance of this operation overall.

Upvotes: 3

Views: 3890

Answers (2)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726849

Your approach indeed has a lot of overhead, because a new List<T> is created on each insertion.

You can speed this up by sorting in place. Consider that after adding the item at the back of the original pre-sorted list all you need to do is to move that item back until you hit an item that is greater than the newly inserted one. You can do it like this:

static void InsertSorted<T>(IList<T> list, T item) where T : IComparable<T> {
    list.Add(item);
    var i = list.Count-1;
    for ( ; i > 0 && list[i-1].CompareTo(item) < 0 ; i--) {
        list[i] = list[i-1];
    }
    list[i] = item;
}

Demo.

Upvotes: 1

Ousmane D.
Ousmane D.

Reputation: 56453

Your current approach is suboptimal as each time you add an element you're sorting the entire list again which can be avoided and you're constructing a new list each time you add an integer to the List<int> which again can be avoided.

As you already have a List<int> I'd use the methods that belong to this class as opposed to using LINQ to avoid the overhead.

What I suggest is to create an extension method as such:

public static class Extensions {
        public static void InsertElementDescending(this List<int> source, 
                int element)
        {
            int index = source.FindLastIndex(e => e > element);
            if (index == 0 || index == -1)
            {
                source.Insert(0, element);
                return;
            }
            source.Insert(index + 1, element);
        }
}

Then the use case would be:

List<int> list = new List<int>();

list.InsertElementDescending(1);
list.InsertElementDescending(2);
list.InsertElementDescending(233);
list.InsertElementDescending(0);
list.InsertElementDescending(-2);

The list will now have the elements in descending order.

Overall this has better performance than your current approach.

Upvotes: 4

Related Questions