c - C でマージソートを行うと、ガベージ値が取得され続けます

Question

私は一般的なマージソートアルゴリズムに取り組んでいます。問題は、おそらく「ソートされた」配列の内容を印刷するときに、ガベージ値を取得し続けることです。

マージソートアルゴリズム:

void merge(void *a, int n, int size, int (*fcmp)(const void *, const void *)){
    int i, j, k, mid=n/2;
    void * temp = (void *)malloc(n*size);

    for(i=0, j=mid, k=0; k<n; k++){
        if((i<mid)&&(j>=  n)){
            memcpy(temp+(k*size), a+i*size, size);
            i++;
        }
        else if((i<mid)&&(fcmp(a + i*size, a+j*size) <= 0)){
            memcpy(temp+(k*size), a+j*size, size);
            j++;
        }
    }

    for(i=0, j=0; j<n; i++, j++)
        memcpy(a+(j*size),temp+(i*size),size);
    free(temp);
}

void genmsort(void *a, int n, int size, int (*fcmp)(const void *, const void *)){
    if(n>1){
        genmsort(a, n/2, size, (int(*)(const void *, const void *)) compnode);
        genmsort(a+(n/2)*size, n-n/2, size, (int(*)(const void *, const void *)) compnode);
        merge(a, n, size, (int(*)(const void *, const void *)) compnode);
    }
}

複合ノード機能:

int compnode(node *a, node *b){
    return (strcmp(a->name, b->name));
}

初期化関数:

void init_node(node a[], int n){
int i;
    for(i=0; i<n; i++){
        a[i].stdno=i+1;
        sprintf(a[i].name, "%li", a[i].stdno);
    }
    srand(8);
    for(i=0; i<n; i++)
        genswap(a+i, a+(rand()%n), sizeof(node));
}

そして主な機能：

int main(){
    int n=10;
    clock_t t1, t2;

    node *b;
    b=(node *)malloc(n*sizeof(node));
    init_node(b, n);

    t1=clock();
    genmsort(b, n, sizeof(node), (int(*)(const void *, const void *)) compnode);

    t2=clock();
    free(b);
}

ここで何が問題なのですか？長いコードで申し訳ありませんが、ご理解いただければ幸いです。私はしばらくこのコードで立ち往生しているので、本当に助けていただければ幸いです。

Answer 1

補助的な問題

コメントから質問への転記。

残念compnode()ながら、恐ろしいキャストを経験する必要がないように、正気で書いてください! 2 つのconst void *引数を受け取り、それらをコード内で変換するように記述します (ノーオペレーションになります)。

int compnode(const void *v1, const void *v2)
{
    const node *a = v1;
    const node *b = v2;
    return strcmp(a->name, b->name);
}

また、GCC の拡張機能は使用しないでください。移植性のあるコードを書きたがっている場合、それは悪い習慣です。a+(n/2)*size引数がどこにあるかを書くことはvoid *a、C 標準では未定義の動作です。追加する前にchar *(または 以外の他の型)に変換する必要があります。void *

では、直接渡すのではなく、再帰関数と関数genmnode()に渡す必要があります。fcmpmerge()compnode()

ガニカスは尋ねた：

fcmpの代わりに渡すとはどういう意味compnodeですか?

WhozCraig氏は次のように説明しています。

[It] は、カスタム コンパレータ関数を「汎用」ソート関数にfcmpパラメータとして渡すことを意味します。その関数内で、やみくもcompnodeに再帰呼び出しに渡します。代わりにこれらの再帰呼び出しに渡す必要があります。そうしないとfcmp、「一般的な」イデオロギーが窓の外に出ました。

主な問題

主な問題はあなたのmerge()機能にあります。それへのインターフェースは最も珍しいものです。通常、マージする 2 つの配列とそれぞれのサイズを渡します。配列を 1 つ渡し、巧妙なフットワークを行うことを選択しました。メインの for ループのコードがすべてを台無しにします。

void merge(void *a, int n, int size, int (*fcmp)(const void *, const void *)){
    int i, j, k, mid=n/2;
    void * temp = (void *)malloc(n*size);

    for(i=0, j=mid, k=0; k<n; k++){
        if((i<mid)&&(j>=  n)){
            memcpy(temp+(k*size), a+i*size, size);
            i++;
        }
        else if((i<mid)&&(fcmp(a + i*size, a+j*size) <= 0)){
            memcpy(temp+(k*size), a+j*size, size);
            j++;
        }
    }

    for(i=0, j=0; j<n; i++, j++)
        memcpy(a+(j*size),temp+(i*size),size);
    free(temp);
}

末尾のループは単一のmemcpy()操作である必要がありますが、そこにあるものは機能します。

指定されたサイズの要素のa合計を持つ単一の配列 があります。nこれは、要素 [0..mid) の 1 つ (LHS) と要素 [mid..n) のもう 1 つ (RHS) の 2 つのサブ配列として扱われる必要があります。範囲には下限が含まれ、上限は含まれません。

ループ内の最初の条件は、「LHS に要素が残っていて、RHS に何も残っていない場合、LHS 要素を出力にコピーする」ことを示しています。2 番目の条件は、「LHS に要素が残っている場合 (そして、削除により、RHS にも要素が存在する場合)、LHS が RHS よりも小さい場合、RHS 要素を出力にコピーする」ことを示しています。

マージ プロセスを記述するには、さまざまな、最終的には同等の方法がありますが、通常、最も理解しやすい方法は次のとおりです。

while (item left in LHS and item left in RHS)
{
    if (item in LHS is smaller than item in RHS)
        copy LHS to result
    else
        copy RHS to result
}
while (item left in LHS)
    copy item to result
while (item left in RHS)
    copy item to result

実装されたループは、そのロジック、またはそれに相当するものの実装に近づきません。

---

作業コード

これがあなたのコードの私の診断バージョンです。のmemset()一番上は重要でmerge()はありません。tempすべての X にコピーして上書きする必要があります。実際には、そうではありません。

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

typedef struct node node;
struct node
{
    long stdno;
    char name[20];
};

static
void genswap(void *v1, void *v2, size_t size)
{
    char v3[size];
    memmove(v3, v1, size);
    memmove(v1, v2, size);
    memmove(v2, v3, size);
}

static
void print_node(const char *tag, node a[], int n)
{
    printf("%s\n", tag);
    for (int i = 0; i < n; i++)
        printf("%2d: %p %2ld %s\n", i, &a[i], a[i].stdno, a[i].name);
}

static
void merge(void *a, int n, int size, int (*fcmp)(const void *, const void *))
{
    int i, j, k, mid = n/2;
    void *temp = (void *)malloc(n*size);
    memset(temp, 'X', n*size);

    printf("-->> %s\n", __func__);
    print_node("Before Merge", (node *)a, n);
    for (i = 0, j = mid, k = 0; k < n; k++)
    {
        if ((i < mid) && (j >= n))
        {
            memcpy(temp+(k*size), a+i*size, size);
            i++;
        }
        else if ((i < mid) && (fcmp(a + i*size, a+j*size) <= 0))
        {
            memcpy(temp+(k*size), a+j*size, size);
            j++;
        }
    }
    print_node("Mid Merge", (node *)temp, n);

    for (i = 0, j = 0; j < n; i++, j++)
        memcpy(a+(j*size), temp+(i*size), size);
    free(temp);
    print_node("After Merge", (node *)a, n);
    printf("<<-- %s\n", __func__);
}

static
void genmsort(void *a, int n, int size, int (*fcmp)(const void *, const void *))
{
    if (n > 1)
    {
        genmsort(a, n/2, size, fcmp);
        genmsort(a+(n/2)*size, n-n/2, size, fcmp);
        merge(a, n, size, fcmp);
    }
}

static
int compnode(const void *v1, const void *v2)
{
    const node *a = v1;
    const node *b = v2;
    printf("%s: (%ld:%s) vs (%ld:%s)\n", __func__, a->stdno, a->name, b->stdno, b->name);
    return(strcmp(a->name, b->name));
}

static
void init_node(node a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        a[i].stdno = i+1;
        sprintf(a[i].name, "%li", a[i].stdno);
    }
    srand(8);
    for (int i = 0; i < n; i++)
        genswap(a+i, a+(rand()%n), sizeof(node));
}

int main(void)
{
    int n = 10;
    node *b = (node *)malloc(n*sizeof(node));

    init_node(b, n);
    print_node("Before:", b, n);
    genmsort(b, n, sizeof(node), compnode);
    print_node("After:", b, n);
    free(b);

    return 0;
}

Answer 2

このコード内の物事の自由度は豊富です。目立たないものもありますが、最終的にはマージ機能です。典型的なマージ アルゴリズムは、いずれかのリストが使い果たされるまで、反復ごとに1 つの項目をターゲット バッファーに移動します。それが発生すると、残りのリストの残りの項目が所定の場所に一括コピーされ、アルゴリズムが終了します。

あなたには根本的な欠陥があります。ここでそれをカバーします。メイン ループは まで実行kされますがn、少なくともそれは正しいです。ただし、if-else-if 条件の最初の式を見てください。

    if((i<mid)&&(j>=  n))
    {
        memcpy(temp+(k*size), a+i*size, size);
        i++;
    }
    else if((i<mid)&&(fcmp(a + i*size, a+j*size) <= 0))
    {
        memcpy(temp+(k*size), a+j*size, size);
        j++;
    }

どちらもを持っているi<midので、これは次のように簡略化できます。

    if (i<mid)
    {
        if (j>=n)
        {
            memcpy(temp+(k*size), a+i*size, size);
            i++;
        }
        else if (fcmp(a + i*size, a+j*size) <= 0))
        {
            memcpy(temp+(k*size), a+j*size, size);
            j++;
        }
    }

つまり、あなたのi-side があなたの -side の前に使い果たされた場合、その時点から何もせず、に達するまでインクリメントするだけです。分割リストの - 側の残りは完全に無視されます。次に、関数の最後で、初期化されていないデータを元の配列のすぐ上にコピーします。jknj

考慮すべきいくつかのこと。まず、コンパレータ関数の要件を定義し、それに固執します。コールバック リクエスタの要件に従うのは、コンパレータの責任です。その逆ではありません。

typedef int (*fn_cmp)(const void*, const void*);

その標準へのコールバックを実装することにより、これを正しく使用します。

// compare two nodes.
int compare_node(const void* lhs, const void* rhs)
{
    const node* lhn = lhs;
    const node* rhn = rhs;
    return (strcmp(lhn->name, rhn->name));
}

これにより、一般的なマージソートもよりクリーンになります。

// generic mergesort algorithm
void genmsort(void *src, unsigned int len, unsigned int size, fn_cmp fcmp)
{
    if (len < 2)
        return;

    unsigned int mid = len/2;
    genmsort(src, mid, size, fcmp);
    genmsort((unsigned char*)src+(mid*size), len - mid, size, fcmp);
    merge(src, mid, len-mid, size, fcmp);
}

読みやすさは別として、以下とあなたのものの最大の違いはmerge、2 番目の長さパラメーターが追加されていることです (これが機能するという事実はボーナスと見なされます)。この値は、最初に渡された単一の長さから推測されたコードです。再帰的なパーティション サイズを計算するときにコード内のまったく別の場所で行ったこと 一貫性や使いやすさを含む複数の理由から、ここでも同じサイズを渡す必要があります)。

以下をご検討ください。このアルゴリズムに注釈を付けたり、より明確にしたりできる場合は、どうすればよいかわかりません。

// merges two lists back to back in a single sequence.
void merge(void *src,
           unsigned int alen, // note parition size.
           unsigned int blen, // and again here.
           unsigned int size,
           fn_cmp fcmp)
{
    void *bsrc = (unsigned char*)src + alen * size;
    void *dst = malloc((alen + blen)*size);
    unsigned int a = 0, b = 0, k = 0;

    for (k=0; k<(alen+blen); ++k)
    {
        // still got a's ?
        if (a < alen)
        {
            // still got b's ?
            if (b < blen)
            {
                // get "lesser" of the two.
                if (fcmp((const unsigned char*)src + a*size,
                         (const unsigned char*)bsrc + b*size) <= 0)
                {
                    // a is less. move it in.
                    memcpy((unsigned char *)dst + k*size,
                           (const unsigned char*)src + a++*size, size);
                }
                else
                {   // b is less. move it in.
                    memcpy((unsigned char *)dst + k*size,
                           (const unsigned char*)bsrc + b++*size, size);
                }
            }
            else
            {   // no more b's. move the rest of the a's
                // into the target and leave.
                memcpy((unsigned char *)dst + k*size,
                       (const unsigned char*)src + a*size, (alen - a)*size);
                k += (alen-a);
            }
        }
        else
        {   // else no a's. move the rest of the b's into
            //  the target and leave.
            memcpy((unsigned char *)dst + k*size,
                   (const unsigned char*)bsrc + b*size, (blen - b)*size);
            k += (blen-b);
        }
    }

    // copy final output.
    memcpy(src, dst, (alen+blen)*size);
    free(dst);
}

最後に、このコードは、コードで非常に悪用された標準に違反するインクリメンタルなどのコンパイラ拡張機能を必要としません。void*このような拡張機能には近づかないことを強くお勧めします。

---

以下は、上記のアルゴリズムとそのインターフェイスを検証するために使用される完全なテスト プログラムです。よくお読みください。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include <time.h>

// simple node definition.
typedef struct node
{
    char name[32];
    int id;
} node;

// compare two nodes.
int compare_node_names(const void* lhs, const void* rhs)
{
    const node* lhn = lhs;
    const node* rhn = rhs;
    return (strcmp(lhn->name, rhn->name));
}

// compare two nodes.
int compare_node_ids(const void* lhs, const void* rhs)
{
    const node* lhn = lhs;
    const node* rhn = rhs;
    return (lhn->id  - rhn->id);
}

// comparator requirements.
typedef int (*fn_cmp)(const void*, const void*);

// merges two lists back to back in a single sequence.
void merge(void *src,
           unsigned int alen, // note parition size.
           unsigned int blen, // and again here.
           unsigned int size,
           fn_cmp fcmp)
{
    void *bsrc = (unsigned char*)src + alen * size;
    void *dst = malloc((alen + blen)*size);
    unsigned int a = 0, b = 0, k = 0;

    for (k=0; k<(alen+blen); ++k)
    {
        // still got a's ?
        if (a < alen)
        {
            // still got b's ?
            if (b < blen)
            {
                // get "lesser" of the two.
                if (fcmp((const unsigned char*)src + a*size,
                         (const unsigned char*)bsrc + b*size) <= 0)
                {
                    // a is less. move it in.
                    memcpy((unsigned char *)dst + k*size,
                           (const unsigned char*)src + a++*size, size);
                }
                else
                {   // b is less. move it in.
                    memcpy((unsigned char *)dst + k*size,
                           (const unsigned char*)bsrc + b++*size, size);
                }
            }
            else
            {   // no more b's. move the rest of the a's
                // into the target and leave.
                memcpy((unsigned char *)dst + k*size,
                       (const unsigned char*)src + a*size, (alen - a)*size);
                k += (alen-a);
            }
        }
        else
        {   // else no a's. move the rest of the b's into
            //  the target and leave.
            memcpy((unsigned char *)dst + k*size,
                   (const unsigned char*)bsrc + b*size, (blen - b)*size);
            k += (blen-b);
        }
    }

    // copy final output.
    memcpy(src, dst, (alen+blen)*size);
    free(dst);
}

// generic mergesort algorithm
void genmsort(void *src, unsigned int len, unsigned int size, fn_cmp fcmp)
{
    if (len < 2)
        return;

    unsigned int mid = len/2;
    genmsort(src, mid, size, fcmp);
    genmsort((unsigned char*)src+(mid*size), len - mid, size, fcmp);
    merge(src, mid, len-mid, size, fcmp);
}

int main()
{
    static const unsigned int N = 50;
    node *data = malloc(N * sizeof(*data));
    int i=0;

    srand((unsigned)time(NULL));
    for (i=0;i<N;++i)
    {
        data[i].id = i+1;
        sprintf(data[i].name, "String%.3d", 1 + rand() % 999);
    }

    // sort on names.
    genmsort(data, N, sizeof(data[0]), compare_node_names);
    for (i=0;i<N;++i)
        printf("%s : %u\n", data[i].name, data[i].id);
    printf("\n");

    // use a different comparator, this time by id.
    genmsort(data, N, sizeof(data[0]), compare_node_ids);
    for (i=0;i<N;++i)
        printf("%s : %u\n", data[i].name, data[i].id);
    printf("\n");

    free(data);

    return 0;
}

出力

String053 : 49
String097 : 38
String104 : 46
String122 : 41
String129 : 8
String139 : 3
String168 : 30
String184 : 22
String222 : 16
String230 : 28
String249 : 4
String265 : 34
String285 : 44
String295 : 20
String298 : 47
String300 : 19
String321 : 2
String375 : 37
String396 : 50
String408 : 13
String430 : 31
String466 : 35
String483 : 24
String484 : 27
String491 : 25
String494 : 39
String507 : 10
String513 : 7
String514 : 11
String539 : 5
String556 : 29
String570 : 43
String583 : 33
String584 : 42
String620 : 15
String632 : 12
String671 : 21
String705 : 23
String710 : 14
String714 : 45
String724 : 18
String733 : 9
String755 : 48
String805 : 36
String814 : 6
String847 : 32
String876 : 40
String893 : 26
String906 : 17
String972 : 1

String972 : 1
String321 : 2
String139 : 3
String249 : 4
String539 : 5
String814 : 6
String513 : 7
String129 : 8
String733 : 9
String507 : 10
String514 : 11
String632 : 12
String408 : 13
String710 : 14
String620 : 15
String222 : 16
String906 : 17
String724 : 18
String300 : 19
String295 : 20
String671 : 21
String184 : 22
String705 : 23
String483 : 24
String491 : 25
String893 : 26
String484 : 27
String230 : 28
String556 : 29
String168 : 30
String430 : 31
String847 : 32
String583 : 33
String265 : 34
String466 : 35
String805 : 36
String375 : 37
String097 : 38
String494 : 39
String876 : 40
String122 : 41
String584 : 42
String570 : 43
String285 : 44
String714 : 45
String104 : 46
String298 : 47
String755 : 48
String053 : 49
String396 : 50