How to sort a struct of a pair of integers using quicksort?

Question

Suppose I have the following struct:

struct Pair {
    int x;
    int y;
}

I want to sort the array by the first element in the pair, i.e. x and then by the second element so if we are given the following:

input:  [(1,2), (1,0), (2,3), (1,4), (2,2)]
output: [(1,0), (1,2), (1,4), (2,2), (2,3)]

Right now I have two functions, one of them sorts the array by first element and the second one sorts it by second element but this is less efficient. How can I iterate through the array once and achieve the desired result?

void sort1(Pair ps[], int size) {
    int i, j;

    for (i = 0; i < size; i++) {
        for (j = i + 1; j < size; j++) {
            if (ps[j].x > ps[j+1].x) {
                Pair temp = ps[j+1];
                ps[j+1] = ps[j];
                ps[j] = temp;
            }
        }
    }
}

void sort2(Pair ps[], int size) {
    int i, j;

    for (i = 0; i < size; i++) {
        for (j = i + 1; j < size; j++) {
            if (ps[j].y > ps[j+1].y) {
                Pair temp = ps[j+1];
                ps[j+1] = ps[j];
                ps[j] = temp;
            }
        }
    }
}

Also, is there a quick way to do this using a built-in sorting function?

but are there any built-in functions in c? In C++ that would be possible. — Jean-François Fabre, Feb 04 '17 at 14:42
to me your sort functions are not quicksort and won't sort correctly even if you just had single values to sort. but to address the issue of sort x first and y second, you need add "else if(ps[j]x == ps[j+1].x) { if (ps[j].y > ps[j+1].y { Pair temp = ps[j+1]; ps[j+1] = ps[j]; ps[j] = temp;}}. also unless you're trying to learn how to implement a quicksort algorithms, there're a quicksort functions already available in c stdlib. type man qsort. — Shiping, Feb 04 '17 at 14:52
@Shiping Your proposed `else if` body is identical to the existing `if` body, so you don't need `else`; you could just merge the conditions. `qsort` uses an unspecified sorting algorithm; it doesn't have to be quicksort. OP's code is bubblesort. — melpomene, Feb 04 '17 at 15:06
Although bubble sort is stable, it is too slow. Especially since you are using two sorting functions. — RoadRunner, Feb 04 '17 at 15:47
@melpomene sorry i was not clear. i was referring to sort1. in the inner loop, it only checked if x is bigger than the other (if is, then swap). the else if clause is to check if two x's are equal (when the first test fails). if is, then compare two y's. this is the way to sort x first, then y second. — Shiping, Feb 04 '17 at 16:14

RoadRunner · Accepted Answer · 2017-02-04T15:42:10.127

You can use qsort() which is a C library implementation of quicksort.

In order to use this function, you need to design a cmp function which compares two x values against one another, and if their are ties, then sort by y.

In order for this to not be cluttered into one cmp function, you can firstly make a smaller function which tests equality of two integers:

int compare_int(const int a , const int b) {
    if (a < b) {
        return -1;
    } else if (a > b) {
        return 1;
    }
    return 0;
}

Then you can integrate this into your main cmp function, which qsort() will be calling. This function can simply be:

int cmp_func(const void *a, const void *b) {
    const pair_t *num1 = (pair_t *)a;
    const pair_t *num2 = (pair_t *)b;

    if (num1->x == num2->x) {
        return compare_int(num1->y, num2->y);
    } else if (num1->x > num2->x) {
        return +1;
    }
    return -1;
}

Then you can simply call qsort() as the following:

qsort(ps, sizeof(ps)/sizeof(ps[0]), sizeof(pair_t), cmp_func);

Here is some example code which does this:

#include <stdio.h>
#include <stdlib.h>

#define ARRAYSIZE(x) ((sizeof(x))/sizeof(x[0])) 

typedef struct {
    int x;
    int y;
} pair_t;

int compare_int(const int a , const int b) {
    if ( a < b ) {
        return -1;
    } else if ( a > b ) {
        return 1;
    }
    return 0;
}

int cmp_func(const void *a, const void *b) {
    const pair_t *num1 = (pair_t *)a;
    const pair_t *num2 = (pair_t *)b;

    if (num1->x == num2->x) {
        return compare_int(num1->y, num2->y);
    } else if (num1->x > num2->x) {
        return +1;
    }
    return -1;
}

void print_array(pair_t ps[], size_t n) {
    printf("[");
    for (size_t i = 0; i < n; i++) {
        printf("(%d,%d)", ps[i].x, ps[i].y);
        if (i != n-1) {
            printf(", ");
        }
    }
    printf("]\n");
}  

int main(void) {
    pair_t ps[] = {{1,2}, {1,0}, {2,3}, {1,4}, {2,2}};

    printf("Input: ");
    print_array(ps, ARRAYSIZE(ps));

    qsort(ps, ARRAYSIZE(ps), sizeof(pair_t), cmp_func);

    printf("Output: ");
    print_array(ps, ARRAYSIZE(ps));

    return 0;
}

Which outputs:

Input: [(1,2), (1,0), (2,3), (1,4), (2,2)]
Output: [(1,0), (1,2), (1,4), (2,2), (2,3)]

Note: your original code, which is implementing bubble sort, has O(n^2) run-time on average. However, if you use qsort() instead, you will be able to achieve a much faster average of O(logN) run-time. This difference will help achieve quicker results if n grows larger.

This is very neat. Can you please explain why in `qsort(ps, ARRAYSIZE(ps), sizeof(pair_t), cmp_func);` the function cmp_func doesn't take any input? — user6005857, Feb 04 '17 at 15:47
@user6005857 have a look at `void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))`. `compar` is a function pointer, therefore simply calling its name is enough. Specifically, `cmp_func` is the function pointer, and `*cmp_func` is the function. You can read [this](http://stackoverflow.com/questions/840501/how-do-function-pointers-in-c-work) for more information on function pointers. They are a bit strange at first, but can be quite handy sometimes. — RoadRunner, Feb 04 '17 at 15:57
@user6005857 `cmp_func(...)` is a function call. `qsort(..., cmp_func(...))` would pass to `qsort` the result of calling `cmp_func`. But here we're doing `qsort(..., cmp_func)`, which passes the `cmp_func` function itself to `qsort`; we're not calling it. This lets `qsort` call `cmp_func` itself, possibly many times, with different arguments. — melpomene, Feb 04 '17 at 17:16

score 1 · Answer 2 · answered Feb 04 '17 at 15:24

You just need a proper function to compare two pairs:

int comparePairs (const void * a, const void * b)
{
  const Pair* A = (const Pair*) a;
  const Pair* B = (const Pair*) b;
  return (A.x == B.x) ? (A.y - B.y) : (A.x - B.x);
}

Then you can use the built-in function qsort.

How to sort a struct of a pair of integers using quicksort?

2 Answers2