ヒープソートの比較回数と交換回数

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
白菜

ヒープソートの比較回数と交換回数

#1

投稿記事 by 白菜 » 1年前

ヒープソートで比較回数と交換回数のcomp++;と交換回数のswap++;を挿入しましたが、実行した所、比較回数と交換回数が0と表示されます。どの場所をどのように修正すれば良いでしょうか?

コード:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define MAX_ELEMENTS    10000 /* 最大のデータ数 */  
#define OFFSET          100   /* データ数の増分値 */  
#define MAX_LINES       10    /* 関数の最大行数 */  
#define MAX_HEAP        1000
  
int  a[MAX_ELEMENTS] ;        /* 探索するデータ領域 */  
  
int  comp, swap      ;        /* 比較回数、交換回数を格納する変数 */  
  
void downheap(int from,int to);  
void init_step(void);  
void print_step(int);  
void print_header(char *);  
int sorted(int);  
  
int main(void){  
  int i;  
  int n; /* データ数 */  
  
  srandom(time(0));           /* 乱数の種を初期設定する */  
  
 /* ランダム入力の場合 */  
  print_header("random");  
  for (n = OFFSET; n <= MAX_ELEMENTS; n += OFFSET) {  
    init_step();               /* comp, swap の初期化 */  
    for (i = 0; i < n; i++) {  
      a[i] = random() % n ;    /* 配列要素に乱数値を設定する */  
    }  
  
    downheap(i,n);         /* ヒープソートを実行 */  
 
    /* ここに降順のチェックをいれる */
    
    /* ここまでに降順のチェックをいれる */
 
 
    print_step(n);             /* 比較回数、交換回数の表示 */  
  }  
  
 /* 昇順にソートされた入力の場合 */  
  print_header("ascending order");  
  for (n = OFFSET; n <= MAX_ELEMENTS; n += OFFSET) {  
    init_step();               /* comp, swap の初期化 */  
    for (i = 0; i < n; i++) {  
      a[i] = i ;               /* 配列要素に昇順のデータ値を設定する */  
    }  
  
    downheap(i,n);         /* ヒープソートを実行 */  
 
    /* ここに降順のチェックをいれる */
    
    /* ここまでに降順のチェックをいれる */
 
    print_step(n);             /* 比較回数、交換回数の表示 */  
  }  
  
 /* 降順にソートされた入力の場合 */  
  print_header("descending order");  
  for (n = OFFSET; n <= MAX_ELEMENTS; n += OFFSET) {  
    init_step();               /* comp, swap の初期化 */  
    for (i = 0; i < n; i++) {  
      a[i] = n - i ;           /* 配列要素に降順のデータ値を設定する */  
    }  
  
    downheap(i,n);         /*  ヒープソートを実行 */  
 
    /* ここに降順のチェックをいれる */
    
    /* ここまでに降順のチェックをいれる */
 
    print_step(n);             /* 比較回数、交換回数の表示 */  
  }  
  
  return 0;  
}  
  
void init_step(void){  
  swap = 0; comp = 0;  
}  
  
void print_header(char *s) {  
  printf("%s\n   n, 比較回数, 交換回数, チェック",s);  
  printf("\n");  
}  
  
void print_step(int n){  
  printf("%4d, %8d, %8d", n, comp, swap);  
  
  if (sorted(n)) { /* 配列が昇順に整列されているかチェック */  
    printf(", sorted\n");  
  } else {  
    printf(", unsorted\n");  
  }  
}  
  
int sorted(int n) {  
  int i;  
  for (i=0; i < n-1; i++)  
    if (a[i] > a[i+1]) return 0;  
  return 1;  
}  
  
int n = 0;
void downheap(int from,int to)
{
    int i, j;
    int val;
    
    val = a[from];
    i = from;
    while (i <= to/2){
        j = i*2;
        comp++;
        if (j+1 <= to && a[j] > a[j+1])
        j++;
        
     
        if(val <= a[j])
        break;
        

        a[i] = a[j];
        i = j;
        
    }
    a[i] = val;
    
}
    void heapsort()
    {
        int i;
        int tmp;
        
        for (i = n/2; i >= 1; i--)
        downheap(i,n);
        
        for (i = n; i >= 2; i--){
            swap++;
            tmp = a[1];
            a[1] = a[i];
            a[i] = tmp;
            downheap(1, i-1);
            
        }
    }

box
記事: 2002
登録日時: 13年前

Re: ヒープソートの比較回数と交換回数

#2

投稿記事 by box » 1年前

もしかして、となりのスレッドと同じ人?
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

白菜

Re: ヒープソートの比較回数と交換回数

#3

投稿記事 by 白菜 » 1年前

box さんが書きました:
1年前
もしかして、となりのスレッドと同じ人?
はい。そうです。プログラム全部載せました。

box
記事: 2002
登録日時: 13年前

Re: ヒープソートの比較回数と交換回数

#4

投稿記事 by box » 1年前

比較回数と交換回数が0と表示されます。
これはいったんわきへ置いておくとして、
ソートの結果自体は正しいんですか?そっちの方が大切ですよね?
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

白菜

Re: ヒープソートの比較回数と交換回数

#5

投稿記事 by 白菜 » 1年前

box さんが書きました:
1年前
比較回数と交換回数が0と表示されます。
これはいったんわきへ置いておくとして、
ソートの結果自体は正しいんですか?そっちの方が大切ですよね?
プログラムは動きますが、100の値の時に、比較回数、交換回数が表示されるだけなので、ソートの結果は出てません。

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: ヒープソートの比較回数と交換回数

#6

投稿記事 by みけCAT » 1年前

ソートする要素の個数と思われる変数nがdownheap関数およびheapsort関数以外からは見えない位置に置かれており、
n = 0 のまま書き換えられていません。
よって、0個の要素をソートすることになり、比較関数および交換回数が0というのは正しい値です。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

白菜

Re: ヒープソートの比較回数と交換回数

#7

投稿記事 by 白菜 » 1年前

みけCAT さんが書きました:
1年前
ソートする要素の個数と思われる変数nがdownheap関数およびheapsort関数以外からは見えない位置に置かれており、
n = 0 のまま書き換えられていません。
よって、0個の要素をソートすることになり、比較関数および交換回数が0というのは正しい値です。
どのよう修正すれば良いでしょうか?

box
記事: 2002
登録日時: 13年前

Re: ヒープソートの比較回数と交換回数

#8

投稿記事 by box » 1年前

コード:

int n = 0;
この文、本当に必要ですか?ってことを言ってるのではないかと思います。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

白菜

Re: ヒープソートの比較回数と交換回数

#9

投稿記事 by 白菜 » 1年前

box さんが書きました:
1年前

コード:

int n = 0;
この文、本当に必要ですか?ってことを言ってるのではないかと思います。

白菜

Re: ヒープソートの比較回数と交換回数

#10

投稿記事 by 白菜 » 1年前

box さんが書きました:
1年前

コード:

int n = 0;
この文、本当に必要ですか?ってことを言ってるのではないかと思います。
試して見ましたが変わりませんでした。

box
記事: 2002
登録日時: 13年前

Re: ヒープソートの比較回数と交換回数

#11

投稿記事 by box » 1年前

試して見ましたが変わりませんでした。
そうですか?
こちらでは、「どこからも呼ばれている形跡がなさそうな」
いちばん下の方にあるheapsortっていう関数で
nが未定義
っていうコンパイルエラーが出ましたが…。
そもそも、heapsortって、必要なんですか?
使ってないんだったら、外せばいいんじゃないでしょうか。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: ヒープソートの比較回数と交換回数

#12

投稿記事 by みけCAT » 1年前

box さんが書きました:
1年前
こちらでは、「どこからも呼ばれている形跡がなさそうな」
いちばん下の方にあるheapsortっていう関数で
nが未定義
っていうコンパイルエラーが出ましたが…。
heapsortは呼ばれていなかったのですね。
見落としました。申し訳ありません。

あらためてコードを読んだところ、
白菜 さんが書きました:
1年前

コード:

    for (i = 0; i < n; i++) {  
      a[i] = random() % n ;    /* 配列要素に乱数値を設定する */  
    }  
  
    downheap(i,n);         /* ヒープソートを実行 */  
という部分において、nは正の値で、
i < n が成り立たなくなるまでiの値を0から1ずつ増やしながらループした直後に
downheap(i,n); を呼んでいるので、この時点でiとnは等しく、1要素のソートとなっています。
よって、やはり比較回数・交換回数が0というのは正常でしょう。
昇順・降順の入力についても同様です。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

box
記事: 2002
登録日時: 13年前

Re: ヒープソートの比較回数と交換回数

#13

投稿記事 by box » 1年前

もしかして、downheap()を呼ぶときに、

コード:

    downheap(i,n);         /* ヒープソートを実行 */  

コード:

    downheap(i,n);         /* ヒープソートを実行 */  

コード:

    downheap(i,n);         /*  ヒープソートを実行 */  
ここ、全部

コード:

    downheap(0, n);
じゃないとダメ、とか?
引数のfrom, toの意味合いからして、そんな気がしないでもない。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: ヒープソートの比較回数と交換回数

#14

投稿記事 by みけCAT » 1年前

box さんが書きました:
1年前

コード:

    downheap(0, n);
じゃないとダメ、とか?
引数のfrom, toの意味合いからして、そんな気がしないでもない。
main関数内でa[n-1]までしか値を設定していないこと、
そしてdownheap関数内でa[to]まで参照されそうなことから考えると、

コード:

    downheap(0, n-1);
の方が良さそうな気がしますね。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

box
記事: 2002
登録日時: 13年前

Re: ヒープソートの比較回数と交換回数

#15

投稿記事 by box » 1年前

確かに。終わりの添字は
n - 1
です。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

box
記事: 2002
登録日時: 13年前

Re: ヒープソートの比較回数と交換回数

#16

投稿記事 by box » 1年前

あと、呼ばれていない
heapsort()
の中でいくら
swap++;
してもダメですよ。>質問者さん
その関数、使いたいんならどっかから呼んであげないと。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

返信

“C言語何でも質問掲示板” へ戻る