c - C の 4 つのインデックスのタプルに基づいて配列を並べ替える

Question

過去 2 日間、具体的な解決策が見つからずに苦労してきた興味深い問題があります。次の入力配列を取るプログラムを C で作成しようとしています。

ステップ 1: 次のように 3 番目の列に基づいて上記の配列をグループ化します (3 番目の列の値に基づいて、4 つの要素のタプル (つまり、各行) のバケットソート:

ステップ 2: 最後に、次のように各バケット内の 4 番目の列に基づいて要素を並べ替えます。

最終出力配列:

1 列目と 2 列目の要素は、上記の並べ替えプロセスでは何の役割も果たしません。

クイックソートまたはバケットソートとそれに続くクイックソートを使用して、さまざまな手法を試しました。何もうまくいっていません。適切なデータ構造を使用して、Cでこれを行う方法を誰かが提案できますか?

score 5 · Accepted Answer

実際には、複数の並べ替えを行う必要はありません。タプルの 2 つのフィールドに基づいて単一の並べ替えを行うことができます。

既存の並べ替えアルゴリズムを使用するだけですが、次のような比較関数を使用します。

if (val[2] != otherval[2])
    return val[2] < otherval[2];
else
    return val[3] < otherval[3];

これは、値が等しい場合を除き、3 番目の列を使用して並べ替えを行います。値が等しい場合は、4 番目の列を使用します。

または、2 つの別々の並べ替えを実行する場合は、最初に 4 番目の列で並べ替え、次に 3 番目の列で並べ替えます。

score 4 · Accepted Answer

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

int cmp(const void *x, const void *y){
    int (*a)[4] = (int(*)[4])x;
    int (*b)[4] = (int(*)[4])y;
    if((*a)[2]==(*b)[2])
        return (*a)[3] - (*b)[3];
    else
        return (*a)[2] - (*b)[2];
}

int main(void){
    int data[][4] = {
        {1,1,5,5},
        {1,1,5,9},
        {2,2,6,2},
        {1,2,5,5},
        {1,3,6,6},
        {1,4,5,1},
        {4,1,5,6},
        {5,2,7,1},
        {1,1,6,0},
        {2,2,5,0}
    };
    int size = sizeof(data)/sizeof(data[0]);
    int i,j;
    qsort(data, size, sizeof(data[0]), cmp);
    //result print
    for(i=0;i<size;++i){
        for(j=0;j<4;++j)
            printf("%d ", data[i][j]);
        printf("\n");
    }
    return 0;
}

score 2 · Accepted Answer

これは実際には非常に簡単に行うことができます。標準の qsort 関数は、2 つの要素を比較するコールバックを受け取ります。要素が部分配列であることを期待するようにコールバックを記述し、Third 要素を使用して最初に比較します。3 番目の要素が等しい場合は、4 番目の要素を使用して比較します。

c - C の 4 つのインデックスのタプルに基づいて配列を並べ替える

3 に答える 3

Related

Reference