3

I am sorting a Dictionary of 10,000 elements using the OrderBy method as shown below and want to know the big O of it. Does anyone know? After Ordering them I then add them to a new Dictionary in that order. There might be a better way of doing this, but it works for my purposes.

Here is my example:

        m_sortedItems = new Dictionary<int,string>();
        foreach(KeyValuePair<int,string> item in collection.OrderBy(key => key.Value)){
            m_sortedItems.Add(item.Key, item.Value);
        }

I checked on msdn but it wasn't listed: http://msdn.microsoft.com/en-us/library/bb534966.aspx

I plus plus
  • 97
  • 8
  • 3
    Dictionary doesn't have an OrderBy; Enumerable does. Since dictionary does not have defined order, there is nothing special to report really. – Marc Gravell Oct 12 '12 at 18:14
  • According to http://stackoverflow.com/questions/2799427/what-guarantees-are-there-on-the-run-time-complexity-big-o-of-linq-methods, Linq's OrderBy uses quicksort O(N log N). – Chris Sinclair Oct 12 '12 at 18:15

2 Answers2

6

Adding a sorted collection inside a regular dictionary makes no sense, since dictionary does not guarantee to mantain the order.This is just do discourage the code you shown in the question: it might works in some cases, but trust me it's not correct. It is necessary to point the fact that by adding the ordered set back to a dictionary will just vanify the sort you did before. You can enumerate the KeyValuePairs in some order and add in a regular list, that will preserve the insertion order, or better use some other data structures. Have a look for example at sorted dictionary. Of course such kind of data structures takes some more time in the insertion phase, while are generally fast in sorting because they are "naturally" ordered. As per documentation, sorted dictionary insertion time is "at best" O(log(n)), I suggest you to investigate the performance also for nearly ordered input set, because sometimes tree based data structures will suffer such situations due to unbalanced tree formation. If this is the case ( I'm not aware on how is implemented internally ) and performance becomes critical, another intersting data structure is the B-Tree.

Felice Pollano
  • 32,832
  • 9
  • 75
  • 115
  • 1
    "some other data structure" might make sense as a `SortedDictionary`. – Servy Oct 12 '12 at 18:18
  • I was doing it wrong. I data I was using had keys hard coded in order already, the keys weren't mixed up, so the data seemed in order. I am now putting them in a list, and ordering them within the list. – I plus plus Oct 12 '12 at 18:36
3

A Dictionary does not have defined order, so adding items in a particular order is not something that you should be doing.

As far as the big O of sorting, O(NlogN) is going to be the benchmark for most sorting algorithms that you will come across.

NominSim
  • 8,447
  • 3
  • 28
  • 38