HeapSortに関する問題

Question

私の仕事は、擬似コードに従ってヒープソートにコードを書き込むことです。入力配列（4 3 2 5 6 7 8 9 12 1）をヒープソートし、printHeapメソッドでそれを印刷する必要があります。私はprintHeapが動作していることを知っています。これは、すでにbuildHeapというメソッド（最大のヒープバイナリツリーを構築するために使用していますが、あなたはすでにそれを知っています:)）と完璧に動作するので、問題はheapSort 。

正常にソートされ、それが想定される方法（親子1、親2など）で印刷されます。問題は、最大値と最後の値12が突然変わります24私は理由を知りません。

コードは以下の通りです：

void heapSort(int a[], int n){ 
int x = n+1; 
int i; 
int temp; 
buildMaxHeap(a, n); 
for (i = n; i >= 1; i--){ 
    temp = a[i]; 
    a[i] = a [0]; 
    a [0] = temp; 
    x--; 
    heapify(a, 0, x); 
} 

void printHeap(int a[], int n){ 

int i; 
printf("graph g { \n"); 
for (i = 0; i < n/2; i++){ 
    printf("%d -- %d\n", a[i], a[left(i)]); 
    if (right(i) < n){ 
     printf("%d -- %d\n", a[i], a[right(i)]); 
    } 
} 
printf("}\n"); 

出力は以下の通りです：

1 2 3 4 5 6 7 8 9 24 
graph g { 
1 -- 2 
1 -- 3 
2 -- 4 
2 -- 5 
3 -- 6 
3 -- 7 
4 -- 8 
4 -- 9 
5 -- 24 
} 

あなたは私が行っている内容を正確に把握ちょうどので、私はここしばらくの.cファイルを添付します： https://onedrive.live.com/redir?resid=8BC629F201D2BC63!26268&authkey=!AFqVlm9AptiZ_xM&ithint=file%2ccを

本当にあなたの助けに感謝します！

乾杯 アリック

Answer 1

さて、あなたは未定義の動作を観察します。 （私は個人的にオンラインIDE上）の代わりに12（24の0を得ました。）

試してみてください。今日のほぼすべての汎用言語で

void heapSort(int a[], int n) 
{ 
    int x = n; /* changed from n+1 */ 
    int i; 
    int temp; 

    buildMaxHeap(a, n); 
    for (i = n-1; i >= 0; i--){ /*<-- changed*/ 
     temp = a[i]; 
     a[i] = a[0]; 
     a[0] = temp; 
     x--; 
     heapify(a, 0, x); 
    } 
} 

あなたの配列は、インデックス0で始まる[徹底した情報を参照してくださいwiki。]配列for (i = n; i >= 1; i--)を間違ってループし、ヒープが最大であるため、最初の要素を処理せず、最後の要素から範囲外に移動しないでください。 nth要素での算術演算は標準で定義されていますが、それはむしろ< nといくつかのポインタの動作を意味するものではありません。

left、rightなどの機能にマクロを使用すると、パフォーマンスが向上し、読みやすくなります。

私はその日を節約し、AlgoDatエクササイズを希望します。