比較回数と交換回数の表示

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

比較回数と交換回数の表示

#1

投稿記事 by はく » 1年前

ヒープソートで比較回数comp++;と交換回数swap++;の挿入場所が分からないです。いろいろな所に試しても、回数表示が0になります。

コード:

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;
        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--){
            tmp = a[1];
            a[1] = a[i];
            a[i] = tmp;
            downheap(1, i-1);
            
        }
    }
    

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

Re: 比較回数と交換回数の表示

#2

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

はく さんが書きました:
1年前
ヒープソートで比較回数comp++;と交換回数swap++;の挿入場所が分からないです。
比較回数は比較をしている部分に

コード:

        j = i*2;
        if (j+1 <= to && (comp++, a[j] > a[j+1])) /* 挿入 */
交換回数は交換をしている部分に

コード:

        for (i = n; i >= 2; i--){
            swap++; /* 挿入 */
            tmp = a[1];
挿入するのが自然でしょう。
はく さんが書きました:
1年前
いろいろな所に試しても、回数表示が0になります。
提示されていない部分にバグがあるかもしれません。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

返信

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