0

I am trying to implement the merge sort algorithm in C. I understand how the algorithm is supposed to work however I am encountering some difficulties with the implementation.

I understand that there are hundreds of examples and source code for it's implementation but I was hoping someone could help me understand why mine is not working correctly.

My code is below and after the code I explain what I have tried so far.

#include <stdio.h>

void merge(int a[], int L[], int R[],int nL, int nR) //nL and nR are the lengths of L[] and R[]
{
   int i = 0 , j = 0, k = 0;

    while(i<nL && j <nR)
    {
        if(L[i] <= R[j]){
            a[k] = L[i];
            i++;
        }
        else{
            a[k] = R[j];
            j++;
        }

        k++;
     }

     while(i < nL){
        a[k] = L[i];
        i++;
        k++;
     }

     while(j < nR) {
        a[k] = R[j];
        j++;
        k++;
     }
}   

void mergesort(int a[],int n)    //n is the length of a[]
{
   if(n < 2) return;     //BASE CASE
   int mid = n / 2;

   int left[mid];
   int right[n-mid];

   for(int i = 0; i < mid; i++)
   {
        left[i] = a[i];
   }

   for(int i = mid; i < n-1; i++)
   {
        right[i-mid] = a[i];
   }

   int nL = sizeof(left) / sizeof(left[0]);
   int nR = sizeof(right) / sizeof(right[0]);

   mergesort(left, nL);
   mergesort(right, nR);
   merge(a,left,right,nL,nR); 
}    


int main(void)
{
    printf("Initial:\n");
    printf("3 4 1 6\n");

    int numbers[4] = {3,4,1,6};
    int n = sizeof(numbers) / sizeof(int);

    mergesort(numbers,n);
    printf("Sorted:\n");
    for(int i =0 ; i < 4; i++)
    {
        printf("%d ", numbers[i]);
    }

    return 0;
}

As it is and with the unsorted array [3,4,1,6] the output is 0 0 1 3. Clearly the 1 and 3 are in the right order relative to each other but the two zeros at the beginning are clearly wrong. At first it seemed to me that I was inserting 4 and 6 to the right and out of bounds of the array.

I used some print statements to try and debug but I haven't been able to figure out what was going on. I even tried to follow my code with gdb but I still could not sort it.

Does any one have any ideas of what might be happening?

4

3 に答える 3

3

merge()コードを書くより慣用的な方法は次のようになります。

void merge(int a[], int L[], int R[],int nL, int nR)
{
    int i = 0, j = 0, k = 0;

    while (i < nL && j < nR)
    {
        if (L[i] <= R[j])
            a[k++] = L[i++];
        else
            a[k++] = R[j++];
    }
    while (i < nL)
        a[k++] = L[i++];  
    while (j < nR)
        a[k++] = R[j++];
}

これは、コードの行数の約半分であり、広い範囲内で、読み取るコードが少ないほど良いです。各ループまたは条件文の後に中括弧を付けることを主張する人がいます。私はそれが必要（または特に役立つ）とは思いませんが、それがあなたの好きなスタイルなら、それを使うことができます.

あなたのmergesort()コードはそれほどたるんでいませんが、次のように変更できます。

void mergesort(int a[],int n)    //n is the length of a[]
{
    if (n < 2)
        return;     //BASE CASE
    int mid = n / 2;
    int left[mid];
    int right[n-mid];

    for (int i = 0; i < mid; i++)
        left[i] = a[i];

    for (int i = mid; i < n; i++)
        right[i-mid] = a[i];

    mergesort(left, mid);
    mergesort(right, n - mid);
    merge(a, left, right, mid, n - mid); 
}

これには、主な問題の修正が含まれます —right配列をロードするループが最後の要素をコピーせずに残していました。

次のようなデバッグ機能を使用します。

void dump_array(const char *tag, int n, int *a)
{
    printf("%s:%d:", tag, n);
    for (int i = 0; i < n; i++)
        printf(" %3d", a[i]);
    putchar('\n');
}

以下を使用して、多くの効果的なデバッグを行うことができます。

void mergesort(int a[],int n)
{
    if (n < 2)
        return;
    int mid = n / 2;
    int left[mid];
    int right[n-mid];

    dump_array("-->>mergesort()", n, a);

    for (int i = 0; i < mid; i++)
        left[i] = a[i];
    dump_array("left", mid, left);

    for (int i = mid; i < n; i++)
        right[i-mid] = a[i];
    dump_array("right", n - mid, right);

    mergesort(left, mid);
    dump_array("merged-L", mid, left);
    mergesort(right, n - mid);
    dump_array("merged-R", n - mid, right);
    merge(a, left, right, mid, n - mid);
    dump_array("<<--mergesort()", n, a);
}

あなたのコードでは、タグ付きの出力は、right期待したものではなく、最後の要素の 0 または半ランダム データを示します。これは、どこに問題があるかについてのヒントになります。dump_array()関数を維持します。持っていると便利な生き物です。これは単純なバージョンです。たとえば、長い配列の中間位置に改行を出力する、より複雑なバージョンを発明できます。

于 2013-09-24T05:01:28.110 に答える
0

これは、複雑さのないマージソートの単純な実装です。配列ポインターと配列内の全体の総数を渡すだけです。 

void merge(int *a, int top)// Array pointer and max entries
{
    int l1, k, l2, u1, u2, size = 1, i, j;
    int *sa;
    sa = (int *)calloc(top, sizeof(int));

    while (size < top)
    {
        l1 = 0;
        k = 0;
        while (l1 + size < top)
        {
            l2 = l1 + size;
            u1 = l2 - 1;
            u2 = ((l2 + size - 1) < top ? l2 + size - 1 : top - 1);

            for (i = l1, j = l2; i <= u1 && j <= u2; )// Merging
            {
                sa[k++] = a[i] <= a[j] ? a[i++] : a[j++];
            }
            for ( ; i <= u1; )
                sa[k++] = a[i++];
            for ( ; j <= u2; )
                sa[k++] = a[j++];
            l1 = u2 + 1;
        }

        for (i = l1; i < top; i++) // For the left outs of the process
            sa[k++] = a[i];

        for (i = 0; i < top; i++)
            a[i] = sa[i];

        size *= 2;
    }
}
于 2013-11-08T20:37:02.933 に答える