4
\$\begingroup\$

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(n^3)\$ now, it would be interesting changing it to \$O(n^2)\$ or something like that.

Side question: This is \$O(n^3)\$, right (I only like \$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>();
                    tempList.AddRange(errorsSorted.GetRange(j, 
                        errorsSorted.Count - j));

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

                    errorsSorted.RemoveRange(j+1, errorsSorted.Count - (j+1));

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

migrated from stackoverflow.com Nov 25 '11 at 8:59

This question came from our site for professional and enthusiast programmers.

  • 6
    \$\begingroup\$ Why aren't you using any of the built-in sorting methods? \$\endgroup\$ – Jon Skeet Nov 25 '11 at 8:58
  • 1
    \$\begingroup\$ Just make Log Comparable and then use the inbuilt method. \$\endgroup\$ – st0le Nov 25 '11 at 9:02
  • \$\begingroup\$ I did what was intuitive for me. I guess it's my skill cap. \$\endgroup\$ – radbyx Nov 25 '11 at 9:07
  • \$\begingroup\$ I don't know if I can make it comparable, since the Log class is located in Log.designer.cs as a partial class. Maybe I should mention that I have a Log.dbml \$\endgroup\$ – radbyx Nov 25 '11 at 9:10
  • \$\begingroup\$ I think for sort algorithms, you should rarely if ever accept anything with worse than O(n log n) runtime =) \$\endgroup\$ – Jens Nov 25 '11 at 11:23
4
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ Looks cool, I while check it out later to day when I get some spare time :) \$\endgroup\$ – radbyx Nov 25 '11 at 12:27
  • \$\begingroup\$ Works very good and reduce the number of lines with 27 thanks :) \$\endgroup\$ – radbyx Dec 2 '11 at 8:21
1
\$\begingroup\$

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);
LinkedList<Log> errorsSorted = new LinkedList<Log>();
foreach (Log error in errors) {
  LinkedListNode<Log> node = errorsSorted.Last;
  while (node != null && error.Date < node.Value.Date) {
    node = node.Previous;
  }
  if (node != null) {
    errorsSorted.AddAfter(node, error);
  } else {
    errorsSorted.AddFirst(error);
  }
}

This is the insertion sort, which has a worst case performance of O(n^2) and a best case performance of O(n). Note that it starts looking through the sorted list from the end instead of the beginning, which gives it the O(n) performance if the list is already sorted.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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