#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);
}
}
ヒープソートの比較回数と交換回数
ヒープソートの比較回数と交換回数
ヒープソートで比較回数と交換回数のcomp++;と交換回数のswap++;を挿入しましたが、実行した所、比較回数と交換回数が0と表示されます。どの場所をどのように修正すれば良いでしょうか?
Re: ヒープソートの比較回数と交換回数
これはいったんわきへ置いておくとして、比較回数と交換回数が0と表示されます。
ソートの結果自体は正しいんですか?そっちの方が大切ですよね?
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
プログラムは思ったとおりには動かない。書いたとおりに動く。
Re: ヒープソートの比較回数と交換回数
ソートする要素の個数と思われる変数nがdownheap関数およびheapsort関数以外からは見えない位置に置かれており、
n = 0 のまま書き換えられていません。
よって、0個の要素をソートすることになり、比較関数および交換回数が0というのは正しい値です。
n = 0 のまま書き換えられていません。
よって、0個の要素をソートすることになり、比較関数および交換回数が0というのは正しい値です。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: ヒープソートの比較回数と交換回数
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
プログラムは思ったとおりには動かない。書いたとおりに動く。
Re: ヒープソートの比較回数と交換回数
そうですか?試して見ましたが変わりませんでした。
こちらでは、「どこからも呼ばれている形跡がなさそうな」
いちばん下の方にあるheapsortっていう関数で
nが未定義
っていうコンパイルエラーが出ましたが…。
そもそも、heapsortって、必要なんですか?
使ってないんだったら、外せばいいんじゃないでしょうか。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
プログラムは思ったとおりには動かない。書いたとおりに動く。
Re: ヒープソートの比較回数と交換回数
heapsortは呼ばれていなかったのですね。
見落としました。申し訳ありません。
あらためてコードを読んだところ、
という部分において、nは正の値で、白菜 さんが書きました: ↑1年前
i < n が成り立たなくなるまでiの値を0から1ずつ増やしながらループした直後に
downheap(i,n); を呼んでいるので、この時点でiとnは等しく、1要素のソートとなっています。
よって、やはり比較回数・交換回数が0というのは正常でしょう。
昇順・降順の入力についても同様です。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: ヒープソートの比較回数と交換回数
もしかして、downheap()を呼ぶときに、
引数のfrom, toの意味合いからして、そんな気がしないでもない。
ここ、全部 じゃないとダメ、とか?
引数のfrom, toの意味合いからして、そんな気がしないでもない。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
プログラムは思ったとおりには動かない。書いたとおりに動く。
Re: ヒープソートの比較回数と交換回数
main関数内でa[n-1]までしか値を設定していないこと、
そしてdownheap関数内でa[to]まで参照されそうなことから考えると、 の方が良さそうな気がしますね。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: ヒープソートの比較回数と交換回数
あと、呼ばれていない
heapsort()
の中でいくら
swap++;
してもダメですよ。>質問者さん
その関数、使いたいんならどっかから呼んであげないと。
heapsort()
の中でいくら
swap++;
してもダメですよ。>質問者さん
その関数、使いたいんならどっかから呼んであげないと。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
プログラムは思ったとおりには動かない。書いたとおりに動く。