98

I have a dictionary in C# like

Dictionary<Person, int>

and I want to sort that dictionary in place with respect to keys (a field in class Person). How can I do it? Every available help on the internet is that of lists with no particular example of in place sorting of Dictionary. Any help would be highly appreciated!

2
  • I'm not sure I understand your question, as a dictionary isn't enumerated in any order? You either iterate through the keys, or the values, which you could easily sort on the fly... Commented Apr 24, 2010 at 18:22
  • This can't possibly be what you actually want. Arrays can be sorted in place, because the result of sorting an array is an array. But a Dictionary isn't an array, so it can't be replaced with the result of sorting its entries. Sort the entries and save the result in an array or List. And the accepted answer is probably not what you want ... entering and accessing entries from a SortedList or SortedDictionary is a lot slower than from a Dictionary.
    – Jim Balter
    Commented Nov 10, 2018 at 18:41

7 Answers 7

178

You can't sort a Dictionary<TKey, TValue> - it's inherently unordered. (Or rather, the order in which entries are retrieved is implementation-specific. You shouldn't rely on it working the same way between versions, as ordering isn't part of its designed functionality.)

You can use SortedList<TKey, TValue> or SortedDictionary<TKey, TValue>, both of which sort by the key (in a configurable way, if you pass an IEqualityComparer<T> into the constructor) - might those be of use to you?

Pay little attention to the word "list" in the name SortedList - it's still a dictionary in that it maps keys to values. It's implemented using a list internally, effectively - so instead of looking up by hash code, it does a binary search. SortedDictionary is similarly based on binary searches, but via a tree instead of a list.

6
  • 2
    Be careful about using SortedList<K,V>, though: it will be very slow if you build a large list (assuming the items are not pre-sorted). Usually you should use SortedDictionary<K,V> instead, or use the third-party BDictionary<K,V> to get performance similar to SortedDictionary without losing the ability to access items by index or "find nearest key".
    – Qwertie
    Commented Feb 26, 2016 at 7:04
  • What's the advantage of binary searches instead of maintaining a hash alongside sorted keys? Why do I care that the elements are ordered if I'm not almost solely doing ordered enumerations? If I care more about single element lookups, but secondarily want to enumerate based on key order, am I stuck managing a separate list of keys a la Steve's answer? If that's my desired use, SortedList & SortedDictionary are actually the wrong tools, right? That is, what if I literally want to sort only the dictionary keys in place?
    – ruffin
    Commented Aug 22, 2018 at 19:38
  • 1
    @ruffin: The advantage is avoiding complexity. Yes, as far as I'm aware there's no built-in "sorted and hashed" collection. Note that such a collection is harder to use as well as build - having to provide both an equality comparison and hash code function, as well as an ordering function. There's also a memory cost to keeping both collections, of course. You'd need to measure the cost of binary searches vs hash lookups for your actual data - you may well find that it's not actually significant unless your collections are vast.
    – Jon Skeet
    Commented Aug 23, 2018 at 5:04
  • @ruffin "What's the advantage of binary searches instead of maintaining a hash alongside sorted keys?" -- memory for the hash table and the time to maintain it when adding or deleting entries. "Why do I care that the elements are ordered" -- if you don't care that the elements are ordered then just use a Dictionary (which I would generally recommend over SortedList or SortedDictionary) "but secondarily want to enumerate based on key order" -- it's trivial to sort the enumerated KeyValuePairs when you occasionally need them: dict.OrderBy(kv => kv.Key)
    – Jim Balter
    Commented Nov 10, 2018 at 18:47
  • 2
    @ruffin "what if I literally want to sort only the dictionary keys in place?" -- there's no such thing -- it's a category mistake. Arrays can be sorted in place ... nothing that isn't an array can be. (Well, with the exception of a linked list with mutable nodes, but sorting such a thing in place would be nuts and very expensive.) But of course you can do something like var array = dict.Keys.ToArray(); array.Sort();
    – Jim Balter
    Commented Nov 10, 2018 at 18:59
31

Try using SortedDictionary

0
19

Due to this answers high search placing I thought the LINQ OrderBy solution is worth showing:

class Person
{
    public Person(string firstname, string lastname)
    {
        FirstName = firstname;
        LastName = lastname;
    }
    public string FirstName { get; set; }
    public string LastName { get; set; }
}

static void Main(string[] args)
{
    Dictionary<Person, int> People = new Dictionary<Person, int>();

    People.Add(new Person("John", "Doe"), 1);
    People.Add(new Person("Mary", "Poe"), 2);
    People.Add(new Person("Richard", "Roe"), 3);
    People.Add(new Person("Anne", "Roe"), 4);
    People.Add(new Person("Mark", "Moe"), 5);
    People.Add(new Person("Larry", "Loe"), 6);
    People.Add(new Person("Jane", "Doe"), 7);

    foreach (KeyValuePair<Person, int> person in People.OrderBy(i => i.Key.LastName))
    {
        Debug.WriteLine(person.Key.LastName + ", " + person.Key.FirstName + " - Id: " + person.Value.ToString());
    }
}

Output:

Doe, John - Id: 1
Doe, Jane - Id: 7
Loe, Larry - Id: 6
Moe, Mark - Id: 5
Poe, Mary - Id: 2
Roe, Richard - Id: 3
Roe, Anne - Id: 4

In this example it would make sense to also use ThenBy for first names:

foreach (KeyValuePair<Person, int> person in People.OrderBy(i => i.Key.LastName).ThenBy(i => i.Key.FirstName))

Then the output is:

Doe, Jane - Id: 7
Doe, John - Id: 1
Loe, Larry - Id: 6
Moe, Mark - Id: 5
Poe, Mary - Id: 2
Roe, Anne - Id: 4
Roe, Richard - Id: 3

LINQ also has the OrderByDescending and ThenByDescending for those that need it.

1
  • This is not really ordering the dictionary, but it is ordering the dictionary as it is being used,' Commented Nov 5, 2022 at 0:10
16

The correct answer is already stated (just use SortedDictionary).

However, if by chance you have some need to retain your collection as Dictionary, it is possible to access the Dictionary keys in an ordered way, by, for example, ordering the keys in a List, then using this list to access the Dictionary. An example...

Dictionary<string, int> dupcheck = new Dictionary<string, int>();

...some code that fills in "dupcheck", then...

if (dupcheck.Count > 0) {
  Console.WriteLine("\ndupcheck (count: {0})\n----", dupcheck.Count);
  var keys_sorted = dupcheck.Keys.ToList();
    keys_sorted.Sort();
  foreach (var k in keys_sorted) {
    Console.WriteLine("{0} = {1}", k, dupcheck[k]);
  }
}

Don't forget using System.Linq; for this.

2
  • "if by chance you have some need to retain your collection as Dictionary" -- the obvious reason to keep it is that it has far faster insertion, deletion, and lookup. As for var keys_sorted = dupcheck.Keys.ToList(); keys_sorted.Sort(); -- simpler is keys_sorted = dupcheck.Keys.OrderBy(k => k).ToList(); ... and if you're going to use the values, then just foreach (var ent in dupcheck.OrderBy(kv => kv.Key)) Console.WriteLine($"{ent.Key} = {ent.Value}");
    – Jim Balter
    Commented Nov 10, 2018 at 19:38
  • 1
    This is not sorting of a Dictionary object, this is just sorting of a display and is a workaround :(
    – Ambuj
    Commented May 6, 2019 at 12:41
7

By design, dictionaries are not sortable. If you need this capability in a dictionary, look at SortedDictionary instead.

7

While Dictionary is implemented as a hash table, SortedDictionary is implemented as a Red-Black Tree.

If you don't take advantage of the order in your algorithm and only need to sort the data before output, using SortedDictionary would have negative impact on performance.

You can "sort" the dictionary like this:

Dictionary<string, int> dictionary = new Dictionary<string, int>();
// algorithm
return new SortedDictionary<string, int>(dictionary);
1
  • If you want to sort the entries by key, just use dictionary.OrderBy(kv => kv.Key)
    – Jim Balter
    Commented Nov 10, 2018 at 19:49
4

Take a look at SortedDictionary, there's even a constructor overload so you can pass in your own IComparable for the comparisons.

Your Answer

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

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