How to sort based on the following criteria?

Question

I have a list of (x,y) pair values. The values are floats between 0,xmax and 0,ymax. I need to sort them by balancing out x&y values with more preference to x.

This is a pictorial representation of how I am planning to do my sorting.

The numbers 1,2,3.... and arrows represent the order (and direction) in which i want the values to be selected first. For eg., in this case, i want the value pairs to be sorted as: 1. x1,y1 2. x2,y2 3. x3,y3 4. x4,y4 5. x5,y5

I don't know how to start implementing this because the values are floats. A rough outline of the algorithm to start with would be helpful.

Edit: A more detailed explanation

1. if x val and y values are close to max, that means I want that at the top of my list (most desirable).

2. Upto a certain limit (lim), I want to clearly give 'x' more priority, so (x=xmax , y=lim) is better than (x=xmax-1, y=ymax). --(represented by light blue arrows)

3. If x and y values are below the 'limit mark', then I need to have a close balancing of x&y, with a "slight" priority to x.

Answer 1

Each point (x,y) falls into one of the following four regions:

    y ^
      │ B │ A    Region definitions:
      │   │      A) (x >= m) || (y >= m)
    m ┼   ┼──    B) (x < m && y < m) && (y > x)
      │  ╱       C) (x < m && y < m) && (x > y)
      │ D   C    D) (x < m && y < m) && (x == y)
      │╱      
      ┼───┼──>x
          m

It seems to me that if you sort by decreasing x then decreasing y in region A, and by decreasing min(x,y) then by decreasing max(x,y) in the other regions; with region A sorted before regions B, C, or D, with points otherwise equal in regions B, C, and D are sorted C first, you achieve the sort order the OP desires. See bottom of this answer for an example ordering in (0..9, 0..9) with limit 5.

That is:

Sort A first
   In A, sort decreasing by x, then decreasing by y

Sort decreasing by min(x,y), then decreasing by max(x,y)
If tied, the point with the largest x goes first

If we have

typedef struct {
    double  x;
    double  y;
} point;

we can sort an array of points using e.g.

#include <stdlib.h>

static __thread double  point_sort_limit;

static int point_sort_cmp(const void *ptr1, const void *ptr2)
{
    const point p1 = *(const point *)ptr1;
    const point p2 = *(const point *)ptr2;
    const int   a1 = (p1.x >= point_sort_limit) && (p1.y >= point_sort_limit);
    const int   a2 = (p2.x >= point_sort_limit) && (p2.y >= point_sort_limit);

    if (a1 && !a2)
        return -1;
    if (!a1 && a2)
        return +1;

    if (a1 && a2) {
        /* Both points in the region above the limits */
        if (p1.x > p2.x)
            return -1;
        if (p1.x < p2.x)
            return +1;
        if (p1.y > p2.y)
            return -1;
        if (p1.y < p2.y)
            return +1;

        /* p1 == p2. */
        return 0;
    } else {
        const double min1 = (p1.x <= p1.y) ? p1.x : p1.y;
        const double max1 = (p1.x <= p1.y) ? p1.y : p1.x;
        const double min2 = (p2.x <= p2.y) ? p2.x : p2.y;
        const double max2 = (p2.x <= p2.y) ? p2.y : p2.x;

        if (min1 > min2)
            return -1;
        if (min1 < min2)
            return +1;
        if (max1 > max2)
            return -1;
        if (max1 < max2)
            return +1;

        /* Sort points below the diagonal first. */
        if (p1.x > p2.x)
            return -1;
        if (p1.x < p2.x)
            return +1;

        /* p1 == p2. */
        return 0;
    }
}

void point_sort(point *array, const size_t count, const double limit)
{
    if (count > 1 && array != NULL) {
        point_sort_limit = limit;
        qsort(array, count, sizeof array[0], point_sort_cmp);
    }
}

The C99 __thread keyword makes the point_sort_limit variable to be specific to each thread; that is, each thread will have their own copy of the variable. If you don't use threads in your program, you can safely omit the __thread keyword.

You see, we need to save the limit somewhere, because the standard C qsort() does not allow us to pass any extra parameters to the comparison function. If we use a normal global variable in a multithreaded program, if multiple threads use the point_sort() function at the same time, the point_sort_limit will have incorrect value in most threads. Making the global variable thread-local we avoid that.

If we look at the 100 points in a regular 10×10 grid, i.e. x = [0, 9], y = [0, 9], the order in which they will be sorted by the above function is

    y ^
    9 │  81  64  49  36  25  20  15  10   5   0
    8 │  83  66  51  38  27  21  16  11   6   1
    7 │  85  68  53  40  29  22  17  12   7   2
    6 │  87  70  55  42  31  23  18  13   8   3
   _5_│_ 89  72  57  44  33_|24_ 19  14   9   4
    4 │  91  74  59  46  35 |34  32  30  28  26
    3 │  93  76  61  48  47  45  43  41  39  37
    2 │  95  78  63  62  60  58  56  54  52  50
    1 │  97  80  79  77  75  73  71  69  67  65
    0 │  99  98  96  94  92  90  88  86  84  82
        ────────────────────┼───────────────────> x
         0   1   2   3   4   5   6   7   8   9

when the limit (m or point_sort_limit) is 5.