sort a dictionary <object, List<int>> c#

Question

I would like to sort a list of objects, The structure is a Dictionary<Object, List<int>>

items in the dictionary would be

item_1, (2,2,3)
item_2, (1,3,4)
item_3, (2,3,4)
item_4, (1,2)

once the items are sorted they should appear as

item_4, 1,2
item_2, 1,3,4
item_1, 2,2,3
item_3, 2,3,4

so, essentially I have to sort on the first item in the list, then the second item, then the 3rd items, what would be an easy way of implementing such a solution using linq

Answer 1

You can sort dictionary values in separate list using a custom comparison method:

  static void Main()
  {
        var map = new Dictionary<object, IList<int>>();

        map.Add("item_1", new int[] { 2, 2, 4 });
        map.Add("item_2", new int[] { 1, 3, 4 });
        map.Add("item_3", new int[] { 2, 3, 4 });
        map.Add("item_4", new int[] { 1, 2});

        var list = new List<KeyValuePair<object, IList<int>>>(map);

        list.Sort(CompareSequences);


        foreach(var item in list)
        {
            Console.WriteLine("{0} ({1})", item.Key, string.Join<int>("," , item.Value));
        }

  }



    static int CompareSequences(KeyValuePair<object, IList<int>> left, 
        KeyValuePair<object, IList<int>> right)
    {
         int count = Math.Min(left.Value.Count, right.Value.Count);

        for (int i = 0; i < count; ++i)
        {
            if (left.Value[i] < right.Value[i])
            {
                return -1;
            }

            if (left.Value[i] > right.Value[i])
            {
                return 1;
            }
        }

        if (right.Value.Count > count)
        {
            return -1;
        }

        if (left.Value.Count  > count)
        {
            return 1;
        }

        return 0;
    }

One difference with OrderBy() sorting is that sorting algorithm in List.Sort() is not stable. But it uses less memory and fewer temporary objects

Answer 2

What you need is a custom comparer that can compare a sequence of values based on the items in that sequence, rather than based on the reference to the sequence itself (given that most sequences don't override the default equality behavior). This is fairly straightforward:

public class SequenceComparer<T> : IComparer<IEnumerable<T>>
{
    private IComparer<T> comparer;
    public SequenceComparer(IComparer<T> comparer = null)
    {
        this.comparer = comparer ?? Comparer<T>.Default;
    }

    public int Compare(IEnumerable<T> x, IEnumerable<T> y)
    {
        using (var first = x.GetEnumerator())
        using (var second = y.GetEnumerator())
        {
            while (true)
            {
                var hasFirst = first.MoveNext();
                var hasSecond = second.MoveNext();
                if (hasFirst && !hasSecond)
                    return 1;
                if (hasSecond && !hasFirst)
                    return -1;
                if (!hasFirst && !hasSecond)
                    return 0;
                var comparison = comparer.Compare(first.Current, second.Current);
                if (comparison != 0)
                    return comparison;
            }
        }
    }
}

You can then order the items in your collection using this comparer:

var query = dictionary.OrderBy(pair => pair.Value, new SequenceComparer<int>());

If you want the items in the sequence to sort based on their ordered values, and the sequences are not already ordered, then you can add an ordering of the inner sequences into the query:

var query = dictionary.OrderBy(pair => pair.Value.OrderBy(x => x), 
    new SequenceComparer<int>());