C# List<> Sort by x then y

Question

Similar to this question, but in 2.0, we want to sort by one element, then another. we want to achieve the functional equivalent of SELECT * from Table ORDER BY x, y

We have a class that contains a number of sorting functions, and we have no issues sorting by one element. For example:

public class MyClass {
    public int x;
    public int y;
}  

List<MyClass> MyList;

public void SortList() {
    MyList.Sort( MySortingFunction );
}

And we have the following in the list:

Unsorted     Sorted(x)     Desired
---------    ---------    ---------
ID   x  y    ID   x  y    ID   x  y
[0]  0  1    [2]  0  2    [0]  0  1
[1]  1  1    [0]  0  1    [2]  0  2
[2]  0  2    [1]  1  1    [1]  1  1
[3]  1  2    [3]  1  2    [3]  1  2

I think we are looking for some way to implement a stable sort, but I'm happy to take any suggestions!

edit:

OK, as often seems to be the case, the act of asking the question has released a mental block!

@nobugz - I implemented this just before I saw your answer! Thanks, that's the way to do it in this case. Except I don't use anonymous methods, 'cause I've got a few different sorts for this class.

@Jonathan Holland - If I need to add another sort I'll use something like yours!

@Bill The Lizard - that MS link refreshed my memory!

Answer 1

One quick and dirty way would be to put all the data into a data table and the just use the built in sort command with the data table to achieve the 2 way sort and the iterate from the sorted list back into the 2 dimensional objects that you started with.

Answer 2

List<SomeClass>() a;
List<SomeClass> b = a.OrderBy(x => x.x).ThenBy(x => x.y).ToList();
etc.

Also see ThenByDecending;

edit: sorry didn't notice the 2.0

Answer 3

You need to implement the IComparer interface. Here's a good post with example code.

Answer 4

You don't need a stable sort if you compare all members. For example:

public void SortList() {
  MyList.Sort(delegate(MyClass a, MyClass b)
  {
    int xdiff = a.x - b.x;
    if (xdiff != 0) return xdiff;
    return a.y - b.y;
  });
}

Answer 5

The trick is to implement a stable sort. I've created a Widget class that can contain your test data:

public class Widget : IComparable
{
    int x;
    int y;
    public int X
    {
        get { return x; }
        set { x = value; }
    }

    public int Y
    {
        get { return y; }
        set { y = value; }
    }

    public Widget(int argx, int argy)
    {
        x = argx;
        y = argy;
    }

    public int CompareTo(object obj)
    {
        int result = 1;
        if (obj != null && obj is Widget)
        {
            Widget w = obj as Widget;
            result = this.X.CompareTo(w.X);
        }
        return result;
    }

    static public int Compare(Widget x, Widget y)
    {
        int result = 1;
        if (x != null && y != null)                
        {                
            result = x.CompareTo(y);
        }
        return result;
    }
}

I implemented IComparable, so it can be unstably sorted by List.Sort().

However, I also implemented the static method Compare, which can be passed as a delegate to a search method.

I borrowed this insertion sort method from C# 411:

 public static void InsertionSort<T>(IList<T> list, Comparison<T> comparison)
        {           
            int count = list.Count;
            for (int j = 1; j < count; j++)
            {
                T key = list[j];

                int i = j - 1;
                for (; i >= 0 && comparison(list[i], key) > 0; i--)
                {
                    list[i + 1] = list[i];
                }
                list[i + 1] = key;
            }
    }

You would put this in the sort helpers class that you mentioned in your question.

Now, to use it:

    static void Main(string[] args)
    {
        List<Widget> widgets = new List<Widget>();

        widgets.Add(new Widget(0, 1));
        widgets.Add(new Widget(1, 1));
        widgets.Add(new Widget(0, 2));
        widgets.Add(new Widget(1, 2));

        InsertionSort<Widget>(widgets, Widget.Compare);

        foreach (Widget w in widgets)
        {
            Console.WriteLine(w.X + ":" + w.Y);
        }
    }

And it outputs:

0:1
0:2
1:1
1:2
Press any key to continue . . .

This could probably be cleaned up with some anonymous delegates, but I'll leave that up to you.

EDIT: And NoBugz demonstrates the power of anonymous methods...so, consider mine more oldschool :P