How can I sort HybridDictionary in C#?

Question

Hello, How can I sort HybridDictionary in C#?

 HybridDictionary myCol = new();
 myCol.Add("Braeburn Apples", "1.49");
 myCol.Add("Fuji Apples", "1.29");
 myCol.Add("Gala Apples", "1.49");
 myCol.Add("Golden Delicious Apples", "1.29");
 myCol.Add("Granny Smith Apples", "0.89");
 myCol.Add("Red Delicious Apples", "0.99");
 myCol.Add("Plantain Bananas", "1.49");
 myCol.Add("Yellow Bananas", "0.79");
 myCol.Add("Strawberries", "3.33");
 myCol.Add("Cranberries", "5.98");
 myCol.Add("Navel Oranges", "1.29");
 myCol.Add("Grapes", "1.99");
 myCol.Add("Honeydew Melon", "0.59");
 myCol.Add("Seedless Watermelon", "0.49");
 myCol.Add("Pineapple", "1.49");
 myCol.Add("Nectarine", "1.99");
 myCol.Add("Plums", "1.69");
 myCol.Add("Peaches", "1.99");

Answer 1

Ok, let's start by initializing the dictionary:

using System.Collections.Specialized;
using Spectre.Console;

HybridDictionary myCol = new()
{
    { "Braeburn Apples", "1.49" },
    { "Fuji Apples", "1.29" },
    { "Gala Apples", "1.49" },
    { "Golden Delicious Apples", "1.29" },
    { "Granny Smith Apples", "0.89" },
    { "Red Delicious Apples", "0.99" },
    { "Plantain Bananas", "1.49" },
    { "Yellow Bananas", "0.79" },
    { "Strawberries", "3.33" },
    { "Cranberries", "5.98" },
    { "Navel Oranges", "1.29" },
    { "Grapes", "1.99" },
    { "Honeydew Melon", "0.59" },
    { "Seedless Watermelon", "0.49" },
    { "Pineapple", "1.49" },
    { "Nectarine", "1.99" },
    { "Plums", "1.69" },
    { "Peaches", "1.99" }
};

Now let's output this dictionary (using the Spectre.Console.Table class):

void OutputDictionary(HybridDictionary dic)
{
    Table table = new();
    table.AddColumns("Key", "Value");
    foreach (string key in dic.Keys)
    {
        table.AddRow(key, dic[key]?.ToString() ?? String.Empty);
    }
    AnsiConsole.Write(table);
}

OutputDictionary(myCol);

The result:

┌─────────────────────────┬───────┐
│ Key                     │ Value │
├─────────────────────────┼───────┤
│ Navel Oranges           │ 1.29  │
│ Pineapple               │ 1.49  │
│ Cranberries             │ 5.98  │
│ Strawberries            │ 3.33  │
│ Grapes                  │ 1.99  │
│ Peaches                 │ 1.99  │
│ Nectarine               │ 1.99  │
│ Plums                   │ 1.69  │
│ Plantain Bananas        │ 1.49  │
│ Braeburn Apples         │ 1.49  │
│ Red Delicious Apples    │ 0.99  │
│ Fuji Apples             │ 1.29  │
│ Yellow Bananas          │ 0.79  │
│ Honeydew Melon          │ 0.59  │
│ Seedless Watermelon     │ 0.49  │
│ Gala Apples             │ 1.49  │
│ Granny Smith Apples     │ 0.89  │
│ Golden Delicious Apples │ 1.29  │
└─────────────────────────┴───────┘

Right from the start, we can see that the order we use to insert is not respected when we enumerate, so you cannot rely on inserting in a specific order. Now, how to sort this? The short answer is: You cannot sort it. Why? Because the dictionary has an implementation that takes over sorting in order to provide fast access by key. But this shouldn't stop a developer. If you really need at some point the data sorted by key or value, you should be able to create a "view" of the data sorted the way is needed.

Sorting by Key

The easiest is to sort by key. Let's do some refactoring of our OutputDictionary() method to accept a list of keys instead of fetching the keys from the dictionary. We'll rename it to OutputDictionaryUsingKeys():

void OutputDictionaryUsingKeys(List<string> keys, HybridDictionary dic)
{
    Table table = new();
    table.AddColumns("Key", "Value");
    foreach (string key in keys)
    {
        table.AddRow(key, dic[key]?.ToString() ?? String.Empty);
    }
    AnsiConsole.Write(table);
}

Now we can create the OutputDictionaryBySortedKeys() metohd:

void OutputDictionaryBySortedKeys(HybridDictionary dic)
{
    List<string> sortedKeys = dic.Keys.Cast<string>().ToList();
    sortedKeys.Sort();
    OutputDictionaryUsingKeys(sortedKeys, dic);
}

This method extracts the dictionary keys into a list, and then sorts the list. The output of using this function instead of the original OutputDictionary() one is:.

┌─────────────────────────┬───────┐
│ Key                     │ Value │
├─────────────────────────┼───────┤
│ Braeburn Apples         │ 1.49  │
│ Cranberries             │ 5.98  │
│ Fuji Apples             │ 1.29  │
│ Gala Apples             │ 1.49  │
│ Golden Delicious Apples │ 1.29  │
│ Granny Smith Apples     │ 0.89  │
│ Grapes                  │ 1.99  │
│ Honeydew Melon          │ 0.59  │
│ Navel Oranges           │ 1.29  │
│ Nectarine               │ 1.99  │
│ Peaches                 │ 1.99  │
│ Pineapple               │ 1.49  │
│ Plantain Bananas        │ 1.49  │
│ Plums                   │ 1.69  │
│ Red Delicious Apples    │ 0.99  │
│ Seedless Watermelon     │ 0.49  │
│ Strawberries            │ 3.33  │
│ Yellow Bananas          │ 0.79  │
└─────────────────────────┴───────┘

We have achieved a view of the dictionary that is sorted by key. Note that the dictionary remains unsorted.

Sorting by Value

This is going to be a bit messier. As you can see, the values are seemingly numbers. But are they? In reality, for our program so far, they are not. Why? Because you input them as strings. So they are strings. If we were to sort by value, the sorting rules would be those for strings, not numbers. Do you want to sort numerically? Then don't pass the numbers as strings. If we only wanted the values without tracking the key, the problem would be resolved just like the keys one. Since the dictionary cannot provide the key from a value, we have to resort to a different algorithm to be able to create a list of keys sorted in a way that the resulting view has sorted values. The new method OutputDictionaryBySortedValues() accomplish the feat by obtaining the list of key/value pairs from the dictionary, sorting them by value, then creating a list of keys out of the sorted pairs to finally output using OutputDictionaryUsingKeys():

void OutputDictionaryBySortedValues(HybridDictionary dic)
{
    List<DictionaryEntry> entries = new(dic.Cast<DictionaryEntry>());
    entries.Sort((x, y) => (x.Value ?? String.Empty).ToString().CompareTo(y.Value?.ToString()));
    var keys = from e in entries
               select e.Key.ToString()
        ;
    OutputDictionaryUsingKeys(keys.ToList(), dic);
}

The result is:

┌─────────────────────────┬───────┐
│ Key                     │ Value │
├─────────────────────────┼───────┤
│ Seedless Watermelon     │ 0.49  │
│ Honeydew Melon          │ 0.59  │
│ Yellow Bananas          │ 0.79  │
│ Granny Smith Apples     │ 0.89  │
│ Red Delicious Apples    │ 0.99  │
│ Fuji Apples             │ 1.29  │
│ Navel Oranges           │ 1.29  │
│ Golden Delicious Apples │ 1.29  │
│ Braeburn Apples         │ 1.49  │
│ Gala Apples             │ 1.49  │
│ Pineapple               │ 1.49  │
│ Plantain Bananas        │ 1.49  │
│ Plums                   │ 1.69  │
│ Nectarine               │ 1.99  │
│ Peaches                 │ 1.99  │
│ Grapes                  │ 1.99  │
│ Strawberries            │ 3.33  │
│ Cranberries             │ 5.98  │
└─────────────────────────┴───────┘

Answer 2

Because a HybridDictionary if large, is a hash table, it can not be internally sorted. You can create a new sorted collection from the dictionary with the linq OrderBy. If you want fast hash lookup and sorted access, create both collections.