Sorting vector of x/y coordinates

Question

I have a vector of (u32, u32) tuples which represent coordinates on a 10 x 10 grid. The coordinates are unsorted. Because the standard sort function also didn't yield the result I wanted, I wrote a sort function like this for them:

vec.sort_by(|a, b| {
    if a.0 > b.0 { return Ordering::Greater; }
    if a.0 < b.0 { return Ordering::Less; }

    if a.1 > b.1 { return Ordering::Greater; }
    if a.1 < b.1 { return Ordering::Less; }

    return Ordering::Equal;
});

The resulting grid for my custom function looks like this:

(0/0)   (0/1)   (0/2)   (0/3)   (0/4)   (0/5)   (0/6)   (0/7)   (0/8)   (0/9)
(1/0)   (1/1)   (1/2)   (1/3)   (1/4)   (1/5)   (1/6)   (1/7)   (1/8)   (1/9)
(2/0)   (2/1)   (2/2)   (2/3)   (2/4)   (2/5)   (2/6)   (2/7)   (2/8)   (2/9)
...
(9/0)   (9/1)   (9/2)   (9/3)   (9/4)   (9/5)   (9/6)   (9/7)   (9/8)   (9/9)

This is not what I want, because the lower left should start with (0/0) as I would expect on a mathematical coordinates grid.

I probably can manage to add more cases to the sort algorithm, but is there an easier way to do what I want besides writing a big if .. return Ordering ...; block?

Answer 1

You didn't show how you are populating or printing your tuples, so this is a guess. Flip around and/or negate parts of your coordinates. I'd also recommend using sort_by_key as it's easier, as well as just reusing the existing comparison of tuples:

fn main() {
    let mut points = [(0, 0), (1, 1), (1, 0), (0, 1)];
    points.sort_by_key(|&(x, y)| (!y, x));
    println!("{:?}", points);
}

Adding an extra newline in the output:

[(0, 1), (1, 1),
 (0, 0), (1, 0)]

Originally, this answer suggested negating the value ((-y, x)). However, as pointed out by Francis Gagné, this fails for unsigned integers or signed integers when the value is the minimum value. Negating the bits happens to work fine, but is a bit too "clever".

Nowadays, I would use Ordering::reverse and Ordering::then for the clarity:

fn main() {
    let mut points = [(0u8, 0u8), (1, 1), (1, 0), (0, 1)];
    points.sort_by(|&(x0, y0), &(x1, y1)| y0.cmp(&y1).reverse().then(x0.cmp(&x1)));
    println!("{:?}", points);
}

[(0, 1), (1, 1),
 (0, 0), (1, 0)]