合併排序錯誤C

我想實現合併排序算法。我下面在CLRS book.Here提到的算法是我的代碼合併排序錯誤C

#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+2; 
    n2=end_index-middle_index+1; 
    int sub_arr1[n1],sub_arr2[n2]; 
    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+1]=100; 
    sub_arr2[n2+1]=100; 

    for(i=0;i<=end_index;i++){ 

     l=0,m=0; 
     if(sub_arr1[l]<sub_arr2[m]) 
     {arr[i]=sub_arr1[l++];} 
     else 
     {arr[i]=sub_arr2[m++];} 

    }}

我得到以下輸出

Before sorting. 
52160334 
After sorting. 
22222222 
RUN FINISHED; exit value 0; real time: 10ms; user: 0ms; system: 0ms

自從我服用小整數，我已100作爲sentinel value。我想合併函數有問題。任何幫助讚賞。

來源

2013-10-05 fts

在第一種觀點：'l'和'M'似乎未初始化。（您可以通過在程序中的關鍵點處添加幾個printf（）語句來輕鬆檢查這一點）。同樣強烈建議對索引使用無符號類型（無符號不能溢出，但以模數字爲單位進行摺疊），並在代碼中添加一些斷言/檢查。 – wildplasser

它們已經在塊的最後階段被初始化。 – fts

這意味着他們**總是**零。順便說一句：請不要更新問題來解決錯誤。 – wildplasser

問題很簡單：您的最後loop在merge(...)有問題。

在循環開始之前移動l = 0和m = 0，因爲在每次循環迭代中，對於l和m始終使用值0和1。

將其更改爲：

int l=0, m=0; 
for(i=0;i<=end_index;i++){ 
    if(sub_arr1[l]<sub_arr2[m]) 
    {arr[i]=sub_arr1[l++];} 
    else 
    {arr[i]=sub_arr2[m++];} 

}

來源

2013-10-05 15:35:46 Tauseef

合併排序錯誤C

回答

相關問題