ヒープ並べ替え間違った出力を与える

Question

ヒープソートアルゴリズムで悩まされているが、最終的には分かったが、まだ動作しない。 問題は入力が間違っていることです。プログラムはコンパイルされ、エラーは発生しません。 入力：{1,4,5,3,2,7,8,5,4,7,8,1} 期待される出力：配列がソートされました。

出力：A[i]が5の場合1 2 3 5 7 1 4 4 7 8 5 8

#include <stdio.h> 
#include <stdlib.h> 
#include <conio.h> 

void change(int *a, int *b){ 
    int aux; 
    aux = *a; 
    *a = *b; 
    *b = aux; 
} 
void OrganizeHeap(int *A, int n, int i){ 
    int left = i * 2 + 1, right = i * 2 + 2; 
    int largest = i; 
    if (left < n && A[left] >= A[i]) 
     largest = left; 

    if (right < n && A[right] >= A[i]) 
     largest = right; 

    if (largest != i){ 
     change(&A[i], &A[largest]); 
      OrganizeHeap(A, n, largest); 
    } 
} 
void BuildHeap(int *A, int n){ 
    for (int i = n/2 - 1; i >= 0; i--) 
     OrganizeHeap(A, n, i); 
} 
void HeapSort(int *A, int n){ 
    BuildHeap(A, n); 
    for (int i = n - 1; i >= 0; i--){ 
     change(&A[0], &A[i]); 
     OrganizeHeap(A, i, 0); 
    } 
} 
int main() { 
    int max; 
    int A[] = { 1, 4, 5, 3, 2, 7, 8, 5, 4, 7, 8, 1 }; 
    int n = sizeof(A)/sizeof(int); 
    HeapSort(A, n); 
    for (int i = 0; i < n; i++) 
     printf("%d ", A[i]); 
    _getch(); 
    return 0; 
} 

Answer 1

あなたのコード内の2つの問題

if (right < n && A[right] >= A[i]) 
      largest = right; 

がありますが、A[left]は、7何ですかlargestleftに設定されます。 A [右]が6.A [右]がA[i]より大きい場合、最大値はrightに設定されます。 largestはleftなくrightする必要がありますので、あなたが

if (right < n && A[right] >= A[largest]) //see note below 

ような何かを行うことができます A[left] > A[right]ので、コードを編集した後に、第2の問題はすでに削除されています。

注：

あなただけではなく、あなたが受け取った予想出力とどのような出力が何であるかを含める必要が>=