Sort Points vertically then horizontally

Question

I have an array of Points and i want to sort then both vertically and horizontally.

Should I sort twice?

Answer 1

No, you can write your Custom Sorting With IComparable and IComparer

Answer 2

Using LINQ to objects:

using System;
using System.Linq;
using System.Drawing;

class Example
{
    static void Main()
    {
     Point[] points = new Point[] 
     { 
      new Point(2,2),
      new Point(3,1),
      new Point(3,2),
      new Point(1,3)
     };

     var sortedPoints = points
       .OrderBy(p => p.X)
       .ThenBy(p => p.Y);
    }
}

Answer 3

No you can't just sort twice because the .Net framework Sort() algorithm is an unstable sort, which means that when you sort items, the order they originaly were in is not taken into account, that is, when two items are equal, their position relative to each other will be undefined.

What you will need to do is implement a custom IComparer for the class you are trying to sort and use that comparer when sorting your collection:

class PointComparer : IComparer<Point>
{
    public int Compare(Point x, Point y)
    {
        if (x.Y != y.Y)
        {
            return x.Y - y.Y;
        }
        else
        {
            return x.X - y.X;
        }
    }
}

Usage:

List<Point> list = ...;
list.Sort(new PointComparer());

Answer 4

I can't tell from the question if by "sort both vertically and horizontally" you want to sort them "first vertically then horizontally" (best done in one pass, as the other answers have said) or if you want to sort them so that nearby points in the plane tend to be nearby in the list. If it's the latter, there are space filling curves that can be much better than a pure first-vertical-then-horizontal approach.