合并排序无怪异输出。的不是2的乘方的条目 - Ç [英] Weird output of merge sort for no. of entries not being a power of 2. - c
本文介绍了合并排序无怪异输出。的不是2的乘方的条目 - Ç的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我已经写了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< N / 2;我++)
{
R1 [I] = R [I]
}
对于(i = 0,J = N / 2; J< 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<&R1N功放;&放大器; J< 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<&R1N功放;&安培; K<(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屋!
查看全文