# Optimizing error-sorting method

Posted on

Problem

I just made this sort method. It runs fine and the code looks okay in my eyes.

Is is possible to optimize it so it runs faster? If it’s O(n3)$O\left({n}^{3}\right)$$O(n^3)$ now, it would be interesting changing it to O(n2)$O\left({n}^{2}\right)$$O(n^2)$ or something like that.

Side question: This is O(n3)$O\left({n}^{3}\right)$$O(n^3)$, right (I only like O(n2)$O\left({n}^{2}\right)$$O(n^2)$ and below)?

List<Log> errors = _logHandler.GetErrors(daysBack);
List<Log> errorsSorted = new List<Log>();
for (int i = 0; i < errors.Count; i++)
{
bool inserted = false;
for (int j = 0; j < errorsSorted.Count; j++)
{
if (errors[i].Date < errorsSorted[j].Date)
{
List<Log> tempList = new List<Log>();

errorsSorted[j] = errors[i]; // replace at bigger date index
inserted = true;

// move all bigger dates one place to the right..
{
}
break;
}
}
if (!inserted)
{
errorsSorted.Add(errors[i]); // No date is bigger, add at the end
}
}


Solution

You are just sorting by date, correct? I’d use

using System.Linq;
// ....
List<Log> errors = _logHandler.GetErrors(daysBack);
List<Log> errorsSorted = errors.OrderBy(l => l.Date).ToList();


According to this stackoverflow question, OrderBy uses QuickSort in this case, which usually has a run time of O(n log n).

Well, the obvious would be to use a better algorithm, i.e the built in:

errors.Sort((x,y) => x.Date.CompareTo(y.Date));


What you can do with your code is to use a more effective way to move the elements around. Right now you are moving items from one list to another to instert an item, but the List<T> class is itself capable of inserting an item. It will be a bit faster because you will only be copying the items once instead of twice for each insert.

Much better would be to use a linked list instead. It will be a lot faster because inserting an item will be O(1) instead of O(n) (where n is the number of items that needs to be moved). Something like this (not tested):

List<Log> errors = _logHandler.GetErrors(daysBack);
foreach (Log error in errors) {