没有合并排序的奇怪输出。条目不是 2 的幂。- c

Question

我已经编写了一个用于合并排序的代码来对 c 中的结构数组进行排序，当我不给出时它工作正常。条目作为 2 的幂，但甚至不对其他编号的记录进行排序。的条目。 我想知道我的逻辑哪里错了？？

这是我的代码：

void Mergesort(struct record r[],int n)
{
    int k;
    if(n>1)
    {
        int i,j;
        struct record r1[n/2];
        struct record r2[n-n/2];
        for(i=0,j=n/2;i<n/2 && j<n;i++,j++)
        {
            r1[i]=r[i];
            r2[i]=r[j];
        }
        Mergesort(r1,n/2);
        Mergesort(r2,n/2);
        r=Merge(r1,r2,r,n);
    }

}

struct record * Merge(struct record r1[],struct record r2[],struct record r[],int n)
{
    int i=0,j=0,k=0;
    while(i<n/2 && j<n/2)
    {
        if (strcmp(r1[i].a,r2[j].a)<=0)
        {
            r[k]=r1[i];
            i=i+1;
        }
        else
        {
            r[k]=r2[j];
            j=j+1;
        }
        k=k+1;
    }
    if(i==n/2)
    {
        for(j;j<n/2 && k<n;j++,k++)
        {
            r[k]=r2[j];
        }

    }
    else
    {
        for(i;i<n/2 && k<n;i++,k++)
        {
            r[k]=r1[i];
        }
    }
    return r;
}

任何帮助将不胜感激。！！

Sample Input for 8 entries:

CS003 Vinay 10
CS005 Mouli 9.94
CS010 Gautham 9.94
CS020 Sneha 9.94
CS200 Mohit 9.93
CS012 Aarti 9.9
CS002 Adithya 9.78
CS001 Adithya 9.58

Getting correct output as follows:

CS012 Aarti 9.90
CS002 Adithya 9.78
CS001 Adithya 9.58
CS010 Gautham 9.94
CS200 Mohit 9.93
CS005 Mouli 9.94
CS020 Sneha 9.94
CS003 Vinay 10.00
**[Sorted according to the Names in the record]**

Sample input for 7 entries:

CS003 Vinay 10
CS005 Mouli 9.94
CS010 Gautham 9.94
CS020 Sneha 9.94
CS200 Mohit 9.93
CS012 Aarti 9.9
CS002 Adithya 9.78

Output(Weird):

CS200 Mohit 9.93
CS005 Mouli 9.94
CS020 Sneha 9.94
CS012 Aarti 9.90
CS003 Vinay 10.00
CS010 Gautham 9.94
CS002 Adithya 9.78

[Not at all sorted according to the names]

Answer 1

我将进行以下更改：

void Mergesort(struct record r[],int n)
{
    int k;
    if(n>1)
    {
        int i,j;
        struct record r1[n/2];
        struct record r2[n-n/2];
        for(i=0; i<n/2; i++)
        {
            r1[i]=r[i];
        }
        for(i=0,j=n/2; j < n; i++,j++) // This is required because your previous logic used to skip the last element of j when n is odd.
        {
            r2[i]=r[j];
        }
        Mergesort(r1,n/2);
        Mergesort(r2,n-n/2);//this is 'n - n/2'
        r=Merge(r1,r2,r,n/2, n-n/2); //The sizes are different so pass both
    }

}

struct record * Merge(struct record r1[],struct record r2[],struct record r[],int r1N, int r2N)
{
    int i=0,j=0,k=0;
    while(i<r1N && j<r2N)
    {
        if (strcmp(r1[i].a, r2[j].a)<=0)
        {
            r[k]=r1[i];
            i=i+1;
        }
        else
        {
            r[k]=r2[j];
            j=j+1;
        }
        k=k+1;
    }
    if(i==r1N)
    {
        for(j;j< r2N && k < (r1N + r2N);j++,k++)
        {
            r[k]=r2[j];
        }

    }
    else
    {
        for(i;i < r1N && k < (r1N+r2N); i++,k++)
        {
            r[k] = r1[i];
        }
    }
    return r;
}

Answer 2

这个循环有问题：

for(i=0,j=n/2;i<n/2 && j<n;i++,j++) { ... }

由于您在同一个循环中填充 r1[] 和 r2[]，因此您将用相同数量的项目填充每个数组。但是，如果 n 是奇数，则需要将 r[] 的最后一个剩余元素放入这些数组之一。最简单的解决方案是有两个独立的循环。

Answer 3

你的主要错误是

不考虑 n 的 'halves' 在奇数的情况下，这意味着您的代码仅在 n-s 的所有除法均产生偶数时才有效（直到它下降到 2=1+1);这意味着 n 的起始值必须是 2 的幂。

这反映在以下错误中：

单个 for() 循环来填充 r1[] 和 r2[]，尽管它们的长度不同；
对 Mergesort 的递归调用 r2 传递了错误的长度（n/2 而它应该是 n-n/2）；
将 n 参数单独传递给 Merge 并且 不计算 n-n/2 for r2[] inside Merge .

此外，Mergesort 中声明的未使用变量 k 和函数末尾无用的 r 赋值。

请看下面的代码。

void Mergesort(struct record r[], int n)
{
    if (n > 1)
    {
        int n1 = n/2;
        int n2 = n - n1;
        int i;
        struct record r1[n1];
        struct record r2[n2];

        for (i = 0; i < n1; i++)    // fill r1[] with n1 items from r[]
            r1[i] = r[i];
        for (i = 0; i < n2; i++)    // fill r2[] with n2 items from r[]
            r2[i] = r[n1+i];        // skipping n1 already copied to r1[]

        Mergesort(r1, n1);          // pass appropriate lengths
        Mergesort(r2, n2);
        Merge(r1, r2, r, n1, n2);   // pass arrays with lengths
    }
}

void Merge(struct record r1[], struct record r2[], struct record r[], int n1, int n2)
{
    int i=0, j=0, k=0;
    while (i < n1 && j < n2)        // any items left in both sub-arrays?
    {
        if (strcmp(r1[i].a, r2[j].a) <= 0)  // append the smaller one
            r[k++] = r1[i++];               // or earlier if they're equal
        else
            r[k++] = r2[j++];
    }

    while (i < n1)                  // append the remaining part, if any
        r[k++] = r1[i++];
    while (j < n2)
        r[k++] = r2[j++];
}

您还可以通过删除索引并直接对指针进行操作并递减剩余部分的长度来稍微简化代码：

void Merge(struct record r1[], struct record r2[], struct record r[], int n1, int n2)
{
    while (n1 && n2)        // any items left in both sub-arrays?
    {
        if (strcmp(r1->a, r2->a) <= 0)  // append the smaller one
            *r++ = *r1++, n1--;         // or earlier if they're equal
        else
            *r++ = *r2++, n2--;
    }

    while (n1--)                  // append the remaining part, if any
        *r++ = *r1++;
    while (n2--)
        *r++ = *r2++;
}

没有合并排序的奇怪输出。条目不是 2 的幂。- c

Weird output of merge sort for no. of entries not being a power of 2. - c

c

sorting

mergesort