間違ったマージソート結果

Question

私は通常のマージソート配列コードを書きましたが、これは 関数を 'asize'で、数値ではなく受信する代わりに '1 2 3 4 5 6 7 8 9 10] 私は [-858993460 1 2 3 4 5 6 7 8 9得る定期的なソートされた配列]

あなたがステップオーバーしている。この

void merge_sort(int *a,int first, int last) 
{ 
    int middle; 
      if(first < last) 
      { 
       middle=(first+last)/2; 
       merge_sort(a,first,middle); 
       merge_sort(a,middle+1,last); 
       merge(a,first,middle,last); 
      } 
} 






void main() 
{ 

    int a[] = {9, 7, 2, 3, 5, 4, 1, 8, 6, 10}; 
    int asize= (sizeof a/sizeof a[0]); 
    merge_sort(a, 0, asize); 
For (i = 0; i < 10; i++) 
     printf ("%d ", a[i]); 

Answer 1

あなたの結果の配列が1つの奇妙な値と1つの欠損値を持っているので、最も可能性が高い場合には、むしろasize - 1よりも最後の要素のインデックスとしてasizeを渡す可能性が高い、off-by-oneエラーです。

マージソートに必要なパラメータは、最初と最後のインデックス（ゼロベース）なので、サイズ10の配列の場合、0と9になります。 0と10に現在のコードを渡しています。このため

は、あなたが実際に "アレイ" ソートしている：

{-858993460, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 
\___________________________________/ \/ not your 
       your array     \ array 

：?が（この特定のケースでは）-858993460あるので、

{9, 7, 2, 3, 5, 4, 1, 8, 6, 10, ?} 
\___________________________/ | 
      your array   +-- not your array 

とを、あなたが終わります最初の10個の要素を印刷すると、表示されている出力が得られます。残念ながら、大きな負の値を保持していた変数（またはスタック制御情報など）が、実際に必要な値ではなく、値10で上書きされました。

未定義の動作です。すぐにそれをやめてください。

merge_sort (a, 0, asize); 

へ：

merge_sort (a, 0, asize - 1); 

Answer 2

の理由を見つけるために私を助けてください配列の最後をガベージに入れます。 lastはasize-1である必要があります。つまり、merge_sort(a, 0, asize-1);となります。

Answer 3

merge_sort(a, 0, asize); 

あなたは0asize-1の要素からasize-1すなわちを送信する必要があります。以下は正しいものです！

merge_sort(a, 0, asize-1);