ヒープソートの実装について

Question

ヒープソートのプログラムの作成をしてます。ファイルからデータN個読み込み、ソートして出力するというものです。(昇順)
データNは、
88,176,137,60,198,198,51,137,115,10,187,25,71,26,25,79,37,133,156,126
の20個で、下記のコードを実行すると、
26,10,79,25,25,37,71,85,115,126,133,137,137,156,176,187,198,198
となってしまいます前半部分が上手くソートできてないようなのですが、コードのどの部分が原因なのかわからないため、おしえていただきたいです。

#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* 文字列関数を扱えるようにする */
#define maxN 50

int parent(int i);
void heapsort(int*H, int *A, int n);
void buildheap(int *H, int *A, int n);
void insert(int *H, int i, int *a);
void upheapsort(int *H, int i);
void downheapsort(int *H, int i);

int main(void)
{
  int Data[maxN]; /* 数値を格納する配列は Data */
  int Heap[maxN]; /* ヒープを表す補助配列 */
  int i,N=0; /* N やループで用いる int 型変数 */
  char fname[128];
  FILE *fp; /* ファイル名の変数など必要なものを宣言 */

  printf("input filename: "); /* ファイル名の入力を要求 */
  fgets(fname, sizeof(fname), stdin);
  fname[strlen(fname)-1] = '\0';
  fflush(stdin);

  fp = fopen(fname, "r"); /* ファイルを読み込みモードで開く */
  fscanf(fp, "%d", &N); /* N をファイルから読み込む */
  if (N > maxN){
    printf("N is too large, setting N = %d\n", maxN);
    N = maxN; /* N が max Nを超えるときは警告をした上で */
  } /* N =maxN に設定する */

for (i=0; i<N; i++){
    fscanf(fp, "%d", &Data[i]);
  }
  fclose(fp); /* 開いたファイルを閉じる */
  for (i=0; i<N; i++){
    printf("% d", Data[i]); /* ソート前の数値の出力 */
  }
  printf("\n");

  heapsort(Heap, Data, N); /* ヒープソートを呼ぶ */

  for (i=0; i<N; i++){
    printf("% d", Data[i]); /* ソート後の数値の出力 */
  }
  printf("\n");
  return (0);
}

void heapsort(int*H, int *A, int n)
{
  int i;

  buildheap(H, A, n);
  for(i=1; i<n; i++)
    {
      A[n-i] = H[0];
      H[0] = H[n-i];
      downheapsort(H, n-i-1);
    }
  A[0] = H[0];
}

void buildheap(int *H, int *A, int n)
{
   int i;

   for(i=0;  i<n;  i++)
     {
       insert(H, i, A);
     }
}

void insert(int *H, int i, int *a)
{
  H[i] = a[i];
  upheapsort(H,i); /* 入れ替え */
}

void upheapsort(int *H, int i)
{
  int u;
  int p;
  int j=0;
  int tmp[j];

  u = i;
  p = parent(i); /*親の設定*/
  while(u > 0 && H[p] < H[u])
    {
      tmp[j] = H[p];
      H[p] = H[u];
      H[u] = tmp[j];

      u = p;
      p = parent(p);
    }
}

int parent(int i)
{
  int parent;

  parent = (i-1)/2;

  return parent;
}

void downheapsort(int *H, int i)
{
  int l,r;
  int u = 0;
  int j=0;
  int tmp[j];
  int a = 1;

  while(a == 1)
    {
      if(2*u+1 < i)
        {
          l = 2 * u + 1;
        }
      else
        {
          l = u;
        }

      if(2*u+2 < i)
        {
          r = 2 * u + 2;
        }
      else
        {
          r = u;
        }
if(H[u] < H[r] || H[u] < H[r])
        {
          if(H[l] < H[r])
            {
              tmp[j] = H[u];
              H[u] = H[r];
              H[r] = tmp[j];

              u = r;
            }

          else
            {
              tmp[j] = H[u];
              H[u] = H[l];
              H[l] = tmp[j];

              u = l;
            }
        }
          else
            {
              a = 0;
            }
      }
}

Comments

[y_waiwai]

このままではコードが見づらいので、質門を編集し、<code>ボタンで、出てくる’’’の枠の中にコードを貼り付けてください

[退会済みユーザー]

ご指摘ありがとうございます。

[actorbug]

buildheap と downheapsort の定義は?

[退会済みユーザー]

buildheapでは格納してあるデータをヒープ性を満たすように調節してます。
downheapsortでは大きい値(根)をデータに格納し直した際に、崩れたヒープ性を満たすように調節してます。

[actorbug]

いや、説明が聞きたいわけではなくて、プログラムの中に buildheap の宣言しかなくて定義がないから
このままだとコンパイルできません、という意味です。

[退会済みユーザー]

申し訳ないです。その部分のコードが抜けてしまっていました。

Answer 1

解決済みになっていますが、どのようにして解決したのですか？

次の修正ではないのですか？

-      downheapsort(H, n-i-1);
+      downheapsort(H, n-i);

int j = 0; int tmp[j]; も変ですが。

Comments

[actorbug]

確かに、この修正を入れないと、「4,2,3,1」のような入力がソートできません。見落としてました。

Answer 2

とりあえず、ぱっと見でおかしそうなところを指摘しておきます。

  int j=0;
  int tmp[j];

tmpという配列のサイズが0になってますが、これは意図したことでしょうか。

if(H[u] < H[r] || H[u] < H[r])

||の前後が全く同じ式ですが、これは意図したことでしょうか。

Comments

[退会済みユーザー]

そこの部分の凡ミスでした…
ありがとうございます