Introduction

Sorting arrays of 2D points is a routine operation in computational geometry, computer graphics, and spatial indexing. C's standard library provides qsort, which accepts a custom comparator, making it straightforward to sort by any criterion. This article shows how to define a Point struct and write comparators for x-coordinate, y-coordinate, Euclidean distance, and angular (polar) ordering.

Defining the Point Struct

Start with a simple struct that holds the x and y coordinates. Using double keeps the implementation general enough for both integer and floating-point data.

1#include <stdio.h>
2#include <stdlib.h>
3#include <math.h>
4
5typedef struct {
6    double x;
7    double y;
8} Point;

All comparator functions in the following sections follow the signature required by qsort: they take two const void * arguments and return a negative, zero, or positive integer.

Sorting by X-Coordinate

The most common ordering sorts points left to right. When two points share the same x value, break ties by y.

1int compare_by_x(const void *a, const void *b) {
2    const Point *pa = (const Point *)a;
3    const Point *pb = (const Point *)b;
4    if (pa->x < pb->x) return -1;
5    if (pa->x > pb->x) return  1;
6    // tie-break on y
7    if (pa->y < pb->y) return -1;
8    if (pa->y > pb->y) return  1;
9    return 0;
10}

Avoid the shortcut return (int)(pa->x - pb->x) because casting a small floating-point difference to int truncates values between -1 and 1 to zero, producing incorrect results for closely spaced points.

Sorting by Y-Coordinate

Sorting top-to-bottom (or bottom-to-top) follows the same pattern with x and y swapped.

1int compare_by_y(const void *a, const void *b) {
2    const Point *pa = (const Point *)a;
3    const Point *pb = (const Point *)b;
4    if (pa->y < pb->y) return -1;
5    if (pa->y > pb->y) return  1;
6    if (pa->x < pb->x) return -1;
7    if (pa->x > pb->x) return  1;
8    return 0;
9}

This ordering is useful in sweep-line algorithms that process events from bottom to top across the plane.

Sorting by Distance from the Origin

Sorting by Euclidean distance is needed for nearest-neighbor queries and radial partitioning. Since sqrt is monotonic, you can compare squared distances to avoid the expensive square-root call.

1static double dist_sq(const Point *p) {
2    return p->x * p->x + p->y * p->y;
3}
4
5int compare_by_distance(const void *a, const void *b) {
6    double da = dist_sq((const Point *)a);
7    double db = dist_sq((const Point *)b);
8    if (da < db) return -1;
9    if (da > db) return  1;
10    return 0;
11}

To sort by distance from an arbitrary reference point instead of the origin, pass the reference through a file-scope variable or wrap the comparator in a closure-like pattern using a helper struct.

Angular (Polar) Sorting

Angular sorting arranges points by their angle relative to a reference point, measured counterclockwise from the positive x-axis. This is a core step in algorithms like Graham scan for convex hulls.

1int compare_by_angle(const void *a, const void *b) {
2    const Point *pa = (const Point *)a;
3    const Point *pb = (const Point *)b;
4    double angle_a = atan2(pa->y, pa->x);
5    double angle_b = atan2(pb->y, pb->x);
6    if (angle_a < angle_b) return -1;
7    if (angle_a > angle_b) return  1;
8    // same angle: closer point first
9    return compare_by_distance(a, b);
10}

atan2 returns values in the range [-pi, pi]. If you need all-positive angles (0 to 2*pi), add 2 * M_PI to negative results before comparing. When the reference point is not the origin, subtract its coordinates from each point before computing the angle.

Putting It All Together

Here is a complete example that sorts the same array four different ways.

1void print_points(const char *label, Point pts[], int n) {
2    printf("%s:\n", label);
3    for (int i = 0; i < n; i++)
4        printf("  (%.2f, %.2f)\n", pts[i].x, pts[i].y);
5}
6
7int main(void) {
8    Point pts[] = {
9        {3.0, 4.0}, {1.0, 1.0}, {2.0, 5.0},
10        {0.0, 0.0}, {-1.0, 2.0}
11    };
12    int n = sizeof(pts) / sizeof(pts[0]);
13    Point copy[5];
14
15    memcpy(copy, pts, sizeof(pts));
16    qsort(copy, n, sizeof(Point), compare_by_x);
17    print_points("By X", copy, n);
18
19    memcpy(copy, pts, sizeof(pts));
20    qsort(copy, n, sizeof(Point), compare_by_y);
21    print_points("By Y", copy, n);
22
23    memcpy(copy, pts, sizeof(pts));
24    qsort(copy, n, sizeof(Point), compare_by_distance);
25    print_points("By distance", copy, n);
26
27    memcpy(copy, pts, sizeof(pts));
28    qsort(copy, n, sizeof(Point), compare_by_angle);
29    print_points("By angle", copy, n);
30
31    return 0;
32}

Compile with gcc -O2 -lm points.c -o points. The -lm flag links the math library for atan2 and sqrt.

Performance Considerations

qsort uses an optimized comparison-based sort internally, typically introsort or merge sort depending on the C library. Its average and worst-case complexity is O(n log n). For extremely large point sets (millions of elements), consider these further optimizations:

• Use qsort_r (POSIX) or a wrapper to pass extra context (like a reference point) to comparators without relying on global variables.
• Pre-compute derived values (squared distance, angle) into a parallel array and sort an index array to avoid recomputing inside the comparator.
• For distance-based sorting, skip sqrt entirely by comparing squared distances.

Common Pitfalls

• Subtracting doubles and casting to int. The expression (int)(pa->x - pb->x) silently truncates fractional differences to zero, making the sort non-deterministic for closely spaced points.
• Forgetting the tie-breaker. A comparator that returns 0 for distinct points with equal primary keys produces an unstable order, which breaks algorithms that depend on a total ordering.
• Calling atan2 with both arguments zero. atan2(0, 0) is implementation-defined; filter out the origin before angular sorting if it can appear in the data.
• Modifying the array during sorting. The comparator must never write to the elements it receives; qsort assumes the comparator is a pure function.
• Ignoring NaN coordinates. Any comparison involving NaN returns false, which violates the strict weak ordering that qsort requires and can cause infinite loops or crashes.

Summary

• Represent 2D points as a struct with double x and double y, and use qsort with custom comparators.
• Sort by x-coordinate or y-coordinate using explicit less-than/greater-than checks instead of subtraction casts.
• Compare squared distances rather than actual distances to avoid unnecessary sqrt calls.
• Use atan2 for angular sorting and handle the [-pi, pi] range and origin edge cases.
• Pre-compute derived values for large datasets to avoid redundant work inside the comparator.