using qsort to sort multiple arrays

Question

I have a struct that contains several arrays. I need to be able to sort any of these arrays, and have the elements in the other arrays be shifted according to the sorted array.

struct arrayset
{
int values1[] = { 32, 10, 101, 72, 13, 5 };
int values2[] = { 40, 10, 100, 90, 20, 2 };
int values3[] = { 16, 14, 93, 2, 37, 39 };
};

I understand how to do it with just one, but i'm unsure of an elegant way to change the elements in the other two arrays. I'm not trying to sort the other two arrays, but i want the elements to continue to match post sorting, rather than get mixed up. Any suggestions?

qsort(arrayset.values1,6,sizeof(int), compare);
//values2/3 elements would follow values1's elements

Answer 1

In situations when you have to perform a synchronized rearrangement of several independent data structures you can follow one of the two approaches:

1. An intrusive "internal" approach, mentioned by @wallyk - i.e. provide your own swap function that will swap elements in all three arrays synchronously.
2. A non-intrusive "external" approach - decompose the sorting procedure into two independent steps: first, generate the sorting permutation from the "main" array, then independently apply that sorting permutation to each of the three arrays.

The first approach might be easier to implement, but it has some obvious drawbacks. As the number of data sets grows and/or elements themselves become heavier, the swap function becomes heavier as well. This is not a good thing for sorting algorithms based on physical copying of elements, since such algorithms might relocate (swap) each element more than once.

The second approach is inherently based on indirect, indexed sorting, meaning that it is less sensitive to how heavy element copying is. The second approach copies each of the actual elements only once, when it knows its final position.

To generate the sorting permutation all you need to do is to take an integer index array p initialized with { 0, 1, 2, 3, ... }. Instead of directly sorting values1, sort this index array p to make it produce the proper ordering for your values1 array. (Standard qsort function does not work very well for such applications, since it is contextless.)

After sorting, that index array will serve as your permutation. All you need to do is to rearrange each of your three arrays in accordance with that permutation. It can be done in-place or, easier, out-of-place, depending on what you need.

In your specific example, you will start with index array

p = { 0, 1, 2, 3, 4, 5 }

After sorting it will turn into

p = { 5, 1, 4, 0, 3, 2 }

This is a so-called from-permutation for your values1 array: it tells you that in order to obtain a sorted version of values1, element at position i shall be taken from values1[p[i]]. Now, all you need to do is to generate the rearranged versions of values1, values2 and values3 using the same from-permutation p.

Again, the latter step is easy to do out-of-place and is more difficult to do in-place. Here you can find some relevant implementations of in-place rearrangement for from-permutations: In-place array reordering?

Answer 2

Whenever I am faced with a problem of this type, I grab a qsort implementation and modify it to accept—besides a comparison function—an additional swap function.

In that way you could swap items in all the parallel data.

Answer 3

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

struct arrayset {
    int *values1;
    int *values2;
    int *values3;
};

void custom_sort(struct arrayset *v, size_t size);

int main() {
    struct arrayset work = {
        (int []){ 32, 10, 101, 72, 13, 5 },
        (int []){ 40, 10, 100, 90, 20, 2 },
        (int []){ 16, 14,  93,  2, 37, 39}
    };
    custom_sort(&work, 6);
    for(int i=0;i<6;++i){
        printf("%d, %d, %d\n",
            work.values1[i], work.values2[i], work.values3[i]);
    }
    return 0;
}

typedef struct pair {
    int key, value;
} Pair;

int cmp(const void *x, const void *y){
    int a = ((const Pair*)x)->key;
    int b = ((const Pair*)y)->key;
    return a < b ? -1 : a > b;
}

void custom_sort(struct arrayset *v, size_t size){
    Pair key[size];
    for(int i=0;i<size;++i){
        key[i].key  = v->values1[i];
        key[i].value=i;
    }
    qsort(key, size, sizeof(Pair), cmp);
    int v1[size], v2[size], v3[size];
    memcpy(v1, v->values1, size*sizeof(int));
    memcpy(v2, v->values2, size*sizeof(int));
    memcpy(v3, v->values3, size*sizeof(int));
    for(int i=0;i<size;++i){
        v->values1[i] = v1[key[i].value];
        v->values2[i] = v2[key[i].value];
        v->values3[i] = v3[key[i].value];
    }
}