How can I sort an array that depends on another, with qsort?

Question

Example:

degree =  [2,3,3,2,2,2]

vertex =  [1,2,3,4,5,6]

vertex 1 has degree 2, vertex 2 has degree 3, etc...

I need this solution vertex = [2,3,4,5,6,1]. I want to change vertex using the values of degree. (it does not matter the order of the last 4 numbers (that have the same degree.

I have much more code but I think that with this is okey.

Thanks!

typedef struct {
    u32 Orden;
    u32 Grado;
} ParGradoOrden;

int comGrado (const void * a, const void * b) {
    const u32 x = ((ParGradoOrden *) a)->Grado;
    const u32 y = ((ParGradoOrden *) b)->Grado;
    const u32 xx = ((ParGradoOrden *) a)->Orden;
    const u32 yy = ((ParGradoOrden *) b)->Orden;

    if (x < y)
        return 1;
    else if (x > y)
        return -1;

    if (xx < yy)
        return -1;
    else if (xx > yy)
        return 1;

    return 0;
}

qsort(G->vertices, n, sizeof(ParGradoOrden), comGrado);

Grafostv* ConstruccionDelGrafo()
{
    Grafostv* G = (Grafostv*)malloc(sizeof(Grafostv));
    u32 n = 0; //number of vertexs
    u32 m = 0; //number of edges
    u32 v = 0; //vertex name
    u32 w = 0; // vertex name
    int c = 0; //auxiliar char needed for fgetc function
    char prev = 'a';
    char edge[50] = {0};

    G->m = m;
    G->n = n;
    G->orden = (u32*)malloc(sizeof(u32) * n);
    G->grados = (u32*)malloc(sizeof(u32) * n);
    G->vertices = (u32*)malloc(sizeof(u32*) * n);

    for (u32 i = 0; i < 2*m; ++i)
        G->vecinos[i] = (u32*)malloc(sizeof(u32)*2);

    for (u32 i = 0; i < 2*m; i += 2)
    { 
        if(scanf(" %c %u %u",&prev, &v, &w) != 3 || prev != 'e')
        {
            free(G->color);
            free(G->orden);
            free(G->grados);
            return NULL;
        }
            G->vecinos[i][0] = v;
            G->vecinos[i][1] = w;
            G->vecinos[i+1][0] = w;
            G->vecinos[i+1][1] = v;
    } 
    qsort(G->vecinos, 2*m, 2*sizeof(u32), compare);
    G->vertices[0] = G->vecinos[0][0];
    copiarAVertice(G->vertices,G->vecinos,G->grados, G->indEnVecinos, 2*m);
    memset(G->visitados,0,n*sizeof(u32));
    memcpy(G->orden,G->vertices,n*sizeof(u32)); 
    G->max = Greedy(G);
    printf("terminé Greedy\n");
    return G;
}

Answer 1

I take it that you intend the degree array to retain its present order. If you want to co-sort it with the vertex array, then you'll need to write your own sort routine; qsort will not do that job.

Of course, if you're not co-sorting degree, then there must be a well-defined 1-1 mapping from the values of vertex elements to the indices of degree elements, else there is no way to determine what degree goes with what vertex after sorting begins. That appears to be the case for your example, with vertex values being one greater than the indices of their corresponding degree elements.

To sort the vertex array in terms of degree, without modifying degree, the comparison function presented to qsort must be able to access degree through a file-scope variable. If degree itself is not declared at file scope, then you could add a file-scope pointer variable and set it to point to degree. Of course, this has the limitation that you cannot perform multiple sorting runs simultaneously.

That having been set up, the comparison function uses the vertex numbers to access the vertex degrees from the array, and compares them based on those results. That would look something like this:

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

typedef unsigned int u32;

u32 *vert_degree;

int compare_vertices(const void *v1, const void *v2) {
    u32 degree1 = vert_degree[*(const u32 *)v1 - 1];
    u32 degree2 = vert_degree[*(const u32 *)v2 - 1];
    if (degree1 > degree2) {
        return -1;
    } else if (degree1 < degree2) {
        return 1;
    } else {
        return 0;
    }
}

int main(void) {
    u32 degree[] = {2,3,3,2,2,2};
    u32 vertex[] = {1,2,3,4,5,6};

    vert_degree = degree;
    qsort(vertex, 6, sizeof(vertex[0]), compare_vertices);

    printf("%d", vertex[0]);
    for (int i = 1; i < 6; i++) {
        printf(", %d", vertex[i]);
    }
    putchar('\n');
    return 0;
}

Output:

2, 3, 1, 4, 5, 6

If you happen to be on a glibc-based system (i.e. Linux), then you also have the option of using qsort_r, which accepts auxiliary data such as the degree array, and passes it on to the comparison function (which must therefore accept an additional parameter). That allows you to avoid relying on global variables, but it is specific to glibc.