C - Sort two arrays the same way

Question

So I have two arrays (pointers actually), lets call them a and b. I want to first sort a, then save the exact swaps I did to get that sorted array and apply them to my vector b. Here's a short example of what I mean:

int *a, *b;
//appropriate mallocs
a[0] = 2; a[1] = 3; a[2] = 1;
b[0] = 4; b[1] = 2; b[2] = 3;
//sort a in decreasing order --> a==[3, 2, 1]
//sort b based on sorting of a --> b==[2, 4, 3]

How I could achieve this without writing my own sort function?

Answer 1

This example does what the original question asked for, it sorts two (or more) arrays the same way, without having to combine the array elements into a common structure.

It uses an array of pointers, so the compare function does not need to know which array it is sorting, only the type of the elements being sorted. It could be modified to sort multiple arrays according to one of the arrays.

It creates an array of pointers to a[], uses qsort() to sort the array of pointers according to a[], then uses the sorted pointers to reorder both a[] and b[] in place (with the side effect that the sorted pointers are restored to their initial state).

The reordering time complexity is O(n) as each store places an element in its sorted position.

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

int compare(const void *pp0, const void *pp1)
{
    int i0 = **(int **)pp0;
    int i1 = **(int **)pp1;
    if(i0 > i1)return -1;
    if(i0 < i1)return  1;
    return 0;
}

int main()
{
    int a[3] = {2, 3, 1};
    int b[3] = {4, 3, 2};
    int *pa[3];
    size_t i, j, k;
    int ta, tb;

    /* create array of pointers to a[] */
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        pa[i] = &a[i];

    /* sort array of pointers */
    qsort(pa, sizeof(a)/sizeof(a[0]), sizeof(pa[0]), compare);

    /* reorder a[] and b[] according to the array of pointers */
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++){
        if(i != pa[i]-a){
            ta = a[i];
            tb = b[i];
            k = i;
            while(i != (j = pa[k]-a)){
                a[k] = a[j];
                b[k] = b[j];
                pa[k] = &a[k];
                k = j;
            }
            a[k] = ta;
            b[k] = tb;
            pa[k] = &a[k];
        }
    }

    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        printf("%2d ", a[i]);
    printf("\n");

    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        printf("%2d ", b[i]);
    printf("\n");

    return 0;
}

Answer 2

The better solution is to group the data into an array of structures, then sort that based on the desired key (i.e. the a values):

struct my_data {
  int a;
  int b;
};

struct my_data data[100];

static int data_cmp(const void *a, const void *b)
{
  const struct my_data *da = a, *db = b;

  return da->a < db->a ? -1 : da->a > db->a;
}

qsort(data, sizeof data / sizeof *data, sizeof *data, data_cmp);

This uses qsort() to sort, which is typically highly desirable.