错误的合并功能(归并排序) [英] Error in the Merge Function(Merge Sort)
问题描述
我想通过CLRS的算法书中提到实现合并排序算法。我想出了以下code。
I am trying to implement the merge sort algorithm as mentioned in the algorithms book by CLRS. I have come up with the following code.
#include<stdio.h>
#include<stdlib.h>
void merge_sort(int *arr,int start_index,int end_index);
void merge(int *arr,int start_index,int middle_index,int end_index);
int main(){
int arr[]={5,2,1,6,0,3,3,4}; //8 elements last index 7
int i;
printf("Before sorting.\n");
for(i=0;i<8;i++)
printf("%d,",arr[i]);
merge_sort(arr,0,7);
printf("\nAfter sorting.\n");
for(i=0;i<8;i++)
printf("%d,",arr[i]);
return 0;}
void merge_sort(int *arr,int start_index,int end_index){
int middle_index;
if(start_index<end_index)
{
middle_index=(start_index+end_index)/2;
merge_sort(arr,start_index,middle_index);
merge_sort(arr,(middle_index+1),end_index);
merge(arr,start_index,middle_index,end_index);
}
}
void merge(int *arr, int start_index,int middle_index, int end_index){
int n1,n2,i,l,m;
n1=middle_index-start_index+1;
n2=end_index-middle_index;
int sub_arr1[n1+1],sub_arr2[n2+1];
for(i=0;i<=(n1-1);i++)
sub_arr1[i]=arr[i];
for(i=0;i<=(n2-1);i++)
sub_arr2[i]=arr[middle_index+1+i];
sub_arr1[n1]=100;
sub_arr2[n2]=100;
l=0,m=0;
for(i=0;i<=end_index;i++){
if(sub_arr1[l]<sub_arr2[m])
{arr[i]=sub_arr1[l];
l=l+1;}
else
{arr[i]=sub_arr2[m];
m=m+1;}
}}
There seems to be some error in the merge function due to which I am getting an erroneous output which is as follows.
Before sorting.
5,2,1,6,0,3,3,4,
After sorting.
2,4,100,-1076668400,2,4,100,7,
RUN FINISHED; exit value 0; real time: 0ms; user: 0ms; system: 0ms
因为,我用这种方法排序数量也少,我用100作为一个警戒值。能这样错误的可能来源?任何帮助AP preciated。
Since the numbers that I am sorting with this method are small, I have used 100 as a sentinel value. Can that be a possible source of error? Any help appreciated.
推荐答案
您有您的合并功能的错误:你所忽略的START_INDEX。这些行:
You have an error in your merge function: you are ignoring start_index. These lines:
for(i=0;i<=(n1-1);i++)
sub_arr1[i]=arr[i];
应改为:
for(i=0;i<=(n1-1);i++)
sub_arr1[i]=arr[start_index+i];
和最后一个for循环,应该,而是开始与我= START_INDEX:
And the last for loop, should, instead, start with i = start_index:
for (i=start_index;i<=end_index;i++) { /* ... */ }
我缩进提高一点点。下面是合并的最后工作版本():
I improved indentation a little bit. Here's the final working version of merge():
void merge(int *arr, int start_index,int middle_index, int end_index) {
int n1,n2,i,l,m;
n1=middle_index-start_index+1;
n2=end_index-middle_index;
int sub_arr1[n1+1],sub_arr2[n2+1];
for (i=0;i<=(n1-1);i++)
sub_arr1[i]=arr[start_index+i];
for (i=0;i<=(n2-1);i++)
sub_arr2[i]=arr[middle_index+1+i];
sub_arr1[n1]=100;
sub_arr2[n2]=100;
l=0,m=0;
for (i=start_index;i<=end_index;i++) {
if(sub_arr1[l]<sub_arr2[m]) {
arr[i]=sub_arr1[l];
l=l+1;
}
else {
arr[i]=sub_arr2[m];
m=m+1;
}
}
}
测试和工作。
这篇关于错误的合并功能(归并排序)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!