0

最初の N バイトにはすべてタイプ A のオブジェクトが含まれ、残りのバイトにはタイプ B の要素が含まれる連続したメモリ ブロックがあります。たとえば、タイプ A のオブジェクトが 120 個あり、その後にタイプ B のオブジェクトが 40 個あるとします。

タイプ A とタイプ B はどちらもサイズの異なる構造体ですが、どちらもソートしたい整数メンバー「インデックス」を持っています。基本的に、インデックスでソートされた配列になりたいのですが、現在、データ型でソートされている配列があります。理想的には、インデックスでソートしてからタイプでソートしたいので、次のようになります

Index==1 elements | Index==2 elements | ... | Index==L elements
Type A   | Type B | Type A  |  Type B | ... | Type A| Type B

これまでに思いついた唯一のことは、タイプ A とタイプ B のブロックをインデックスで別々に並べ替えてから、memcopy を使用して物事をシャッフルし、上記のようにすることです。より良い解決策はありますか？

4

3 に答える 3

2

元のアレイはどのように設定されていますか? 同じ配列に異なるタイプを混在させることは、悪い考えのように思えます。それらを同じ配列に入れる必要がある理由はありますか?

それらが同じ配列にある必要がある場合は、共用体を使用することをお勧めします。何かのようなもの

enum myType { A, B };
struct typeA { myType type; int key; ... data ... }
struct typeB { myType type; int key; ... data ... }
union myTypes { typeA myA; typeB myB }
myTypes data[128];

C ライブラリのqsort関数を使用できるようになりました。

別のオプションは、オブジェクトへのポインターの別の配列を使用してから、その補助配列をソートすることです。ただし、各構造体の先頭には何らかのタイプ フィールドが必要です。

于 2013-09-17T08:48:37.857 に答える
1

提案されているポインターの代わりに、タイプとポインターで構成される構造体を使用することをお勧めします (後者は 2 つの異なるポインターの結合体としても)。この場合、同じ場所に ID フィールドがある場合を除き、オブジェクトのタイプを簡単に区別できます。

だから、あなたが持っていると仮定します

struct typeA {
    int whatever;
    int id;
}

struct typeB {
    double whatever;
    int id;
}

あなたは噛まれており、私が言ったようにしなければなりません：

struct typptr {
    enum type { typ_A, typ_B } type;
    union {
        struct typeA * Aptr;
        struct typeB * Bptr;
    }
}

int getID(struct typptr t)
{
    if (t.type == typ_A) {
        return (t.Aptr)->id * 2;
    } else {
        return (t.Bptr)->id * 2 + 1; // have B always sorted after A...
    }
}

このようにして、s をソートするために qsort の cmp 関数を簡単に作成できますstruct typptr。

タイプが「似た形」の場合、

struct typeA {
    int id;
    int whatever;
}

struct typeB {
    int id;
    double whatever;
}

つまり、最初にフィールドがあると、いつでもそれらの1つにキャストしてフィールドidを読み取ることができるため、物事は簡単になります(ただし、これが移植可能かどうかはわかりません) 。idしたがって、ポインターの配列のみが必要であり、型フィールドを省略できます。

于 2013-09-17T09:10:40.377 に答える
0

後のコメントには重要な情報があります-最初はタイプが混在していません。その場合、配列の各部分で個別にソート フェーズを実行し (クイック ソートまたはその他の任意の方法)、2 つの配列間でマージ ソートの最終フェーズを実行できます (追加のスペースを確保できると仮定します)。

それはまだNlogN + N = NlogNです

于 2013-09-17T09:13:28.513 に答える