c - 如何根据其他数组的数量对数组进行排序？

Question

例如，我有这个数组:

G->colour = [2,1,0,1,0,1,0,1,2];
G->vertex = [1,2,3,4,5,6,7,8,9];
G->order = [1,2,3,4,5,6,7,8,9]; //the same of vertex

顶点 1 的颜色为 2，顶点 2 的颜色为 1，等等...
我需要这个解决方案G->order = [1,9,3,5,7,2,4,6,8]。我想使用具有相同颜色的顶点数量按增长顺序排序，即

• 我有两个颜色为 2 的顶点(顶点:1、9)
• 我有三个颜色为 0 的顶点(顶点:3、5、7)
• 我有四个颜色为 1 的顶点(顶点:2、4、6、8)

我有一个按颜色对顶点进行排序的函数 (RMBC)。例如:

G->colour = [2,1,0,1,0,1,0,1,2];
G->order = [1,2,3,4,5,6,7,8,9];

这将返回函数order = [3,5,7,2,4,6,8,1,9]。

此外，我还放置了图形结构以及为顶点着色的贪婪函数。

我还有更多代码，但我认为这样就可以了。

谢谢!

typedef struct Graph
{
    u32** vecinos;
    u32* vertexes;  // Position of vertexes
    u32* color; //Structure type declarations do not support initializers
    u32* grados;
    u32* order; //it has the order of vertex for greedy
    u32* visitados;
    u32 m; //number of edges
    u32 n; // number of vertex
    u32 max; // number of colors
    u32* indEnVecinos;
} Graph;

//RMBC
u32* vert_color;
char RMBC(Graph* G)
{
    vert_color = G->color;
    qsort(G->order, G->n, sizeof(u32), compColoresNormal);
    return 0;
}

int compColoresNormal(const void *v1, const void *v2) {
    u32 color1 = vert_color[*(const u32 *)v1 - 1];
    u32 color2 = vert_color[*(const u32 *)v2 - 1];
    if (color1 < color2)
    {
        return -1;
    }
    else if (color1 > color2)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
// end RMBC

//Greedy 
u32 Greedy(Graph* G)
{
    u32** aux = G->vecinos; 
    u32 max_color = 0;
    u32 nVer = G->n;
    u32* color_vecinos = (u32*)malloc(sizeof(u32) * nVer);
    memset(color_vecinos,0,nVer*sizeof(u32));
    u32 indice = binarySearch(G->vertexes,0,nVer-1,G->order[0]);
    G->color[indice] = 0;
    G->visitados[indice] = 1;
    u32 indice2 = 0;
    u32 reset = 0; 
    for (u32 i = 1; i < nVer; ++i)
    {
        memset(color_vecinos,0,(reset+1)*sizeof(u32));
        indice = binarySearch(G->vertexes,0,nVer-1,G->order[i]);
        G->visitados[indice] = 1;
        u32 color = 0;
        reset = 0;
        for (u32 i = 0; i < G->grados[indice]; ++i)
        {
            indice2 = binarySearch(G->vertexes,0,nVer-1,aux[G->indEnVecinos[indice]+i][1]);
            if(G->visitados[indice2])
            {
                color_vecinos[G->color[indice2]] = 1;
                if(reset < G->color[indice2]) reset = G->color[indice2];
            }
        }
        for (u32 i = 0; i < nVer; ++i)
        {
            if(!color_vecinos[i])
            {
                color = i; 
                break;
            }
        }
        G->color[indice] = color;
        if(color > max_color) max_color = color;
        if(reset < color) reset = color;
        if(reset == nVer) reset--;
    }
    free(color_vecinos);
    printf("terminé Greedy\n");
    return max_color + 1;
}
//end Greedy

Answer 1

你的颜色和顶点的数字小吗？

将这对编码为单个数字，排序并解码

//G->colour = [2,1,0,1,0,1,0,1,2];
//G->vertex = [1,2,3,4,5,6,7,8,9];

colour * 1000 + vertex // based on small values!!

// encode to
// [2001, 1002, 3, 1004, 5, 1006, 7, 1008, 2009]
// sort to
// [2001, 2009, 3, 5, 7, 1002, 1004, 1006, 1008]
// decode to
//G->colour = [2,2,0,0,0,1,1,1,1];
//G->vertex = [1,9,3,5,7,2,4,6,8];