合并排序无怪异输出。的不是2的乘方的条目 - Ç [英] Weird output of merge sort for no. of entries not being a power of 2. - c

问题描述

我已经写了code为归并排序结构，在C正常工作时，我没有给一个数组。条目2的幂，但甚至没有对于其他没有对记录进行排序。的条目。 的我想学哪里是我的逻辑去错了?? 的

下面是我的code：

 无效归并（结构记录r []，INT N）
{
    时int k;
    如果（正→1）
    {
        INT I，J;
        结构记录R1 [N / 2];
        结构记录R2 [N-N / 2];
        对于（I = 0，J = N / 2; I＆下; N / 2和;＆放大器; J＆下; N;我+ +，J ++）
        {
            R1 [I] = R [I]
            R2由[i] = R [J]。
        }
        合并排序（R1中，n / 2）;
        合并排序（R2中，n / 2）;
        R =合并（R1，R2，R，N）;
    }}结构记录*合并（结构记录R1 []，结构记录R2 []，结构记录r []，INT N）
{
    INT I = 0，J = 0，K = 0;
    而（ⅰ＆下; N / 2和;＆放大器; J＆下; N / 2）
    {
        如果（STRCMP（R1 [I]。A，R2 [J] .A）LT; = 0）
        {
            ř[K] = R1 [I];
            I = I + 1;
        }
        其他
        {
             -  [R [K] = R2 [J]。
            当J = J + 1;
        }
        K = K + 1;
    }
    如果（ⅰ== N / 2）
    {
        为（J; J＆下; N / 2和;＆放大器; K＆下; N; J ++，K +）
        {
             -  [R [K] = R2 [J]。
        }    }
    其他
    {
        为（ⅰ; I＆下; N / 2和;＆放大器; K＆下; N;我+ +，K +）
        {
            ř[K] = R1 [I];
        }
    }
    返回ř;
}
 

任何帮助将大大AP preciated !!

  8项采样输入：CS003维奈10
眸里CS005 9.94
CS010 Gautham 9.94
CS020 Sneha 9.94
CS200莫希特9.93
CS012阿尔蒂9.9
CS002 Adithya 9.78
CS001 Adithya 9.58获得正确的输出如下：CS012阿尔蒂9.90
CS002 Adithya 9.78
CS001 Adithya 9.58
CS010 Gautham 9.94
CS200莫希特9.93
眸里CS005 9.94
CS020 Sneha 9.94
CS003 10.00维奈
** [根据记录中的名称排序] **采样输入7条目：CS003维奈10
眸里CS005 9.94
CS010 Gautham 9.94
CS020 Sneha 9.94
CS200莫希特9.93
CS012阿尔蒂9.9
CS002 Adithya 9.78输出（奇怪）：CS200莫希特9.93
眸里CS005 9.94
CS020 Sneha 9.94
CS012阿尔蒂9.90
CS003 10.00维奈
CS010 Gautham 9.94
CS002 Adithya 9.78[不按照名字在所有分类]
 

解决方案

我会做以下修改：

 无效归并（结构记录r []，INT N）
{
    时int k;
    如果（正→1）
    {
        INT I，J;
        结构记录R1 [N / 2];
        结构记录R2 [N-N / 2];
        对于（i = 0; I＆LT; N / 2;我++）
        {
            R1 [I] = R [I]
        }
        对于（i = 0，J = N / 2; J＆LT; N;我++，J ++）//这是必需的，因为你的previous逻辑用于跳过j的最后一个元素，当n为奇数。
        {
            R2由[i] = R [J]。
        }
        合并排序（R1中，n / 2）;
        归并（R2，N-N / 2）; //这是'N  -  N / 2'
        R =合并（R1，R2，R，N / 2，N-N / 2）; //的大小不同，因此同时通过
    }}结构记录*合并（结构记录R1 []，结构记录R2 []，结构记录r []，INT R1N，诠释R2N）
{
    INT I = 0，J = 0，K = 0;
    而（I＆LT;＆R1N功放;＆放大器; J＆LT; R2N）
    {
        如果（STRCMP（R1 [I]。A，R2 [J] .A）LT; = 0）
        {
            ř[K] = R1 [I];
            I = I + 1;
        }
        其他
        {
             -  [R [K] = R2 [J]。
            当J = J + 1;
        }
        K = K + 1;
    }
    如果（我== R1N）
    {
        为（J; J＆下; R2N＆放大器;＆放大器; K＆≤（R1N + R2N）; J ++，K +）
        {
             -  [R [K] = R2 [J]。
        }    }
    其他
    {
        对于（I; I＆LT;＆R1N功放;＆安培; K＆LT;（R1N + 2 N）;我+ +，K +）
        {
            ř[K] = R1 [I];
        }
    }
    返回ř;
}
 

I have written a code for mergesort to sort an array of structures in c it works fine when i give no. of entries as a power of 2 but does not even sort the records for other no. of entries. I Would like to learn where is my logic going wrong??

Here is my code:

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;
}

Any Help would be greatly appreciated.!!

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]

解决方案

I would make the below changes:

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;
}

这篇关于合并排序无怪异输出。的不是2的乘方的条目 - Ç的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！