質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.49%

マージソートの比較回数について

受付中

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 6,279
マージソートについての質問です。
n個の配列データを昇順に並べ替えるプログラムで
配列を比較して出力はできたのですが、その比較回数をどこで数えたらいいのかが分かりません。
下がソースなんですけど、eの位置だと5回しか数えられていないみたいです。
あとどこでどのように数えたらいいのか教えてください。

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

void MergeSort(int x[ ], int left, int right,int n,int *p);
void main(void);

/* 配列 x[ ] の left から right の要素のマージソートを行う */
void MergeSort(int x[ ], int left, int right,int n,int *p)
{
  int temp[n];
  int mid, i, j, k, e=0;
  
  if (left >= right)              /* 配列の要素がひとつなら */
    return;                     /* 何もしないで戻る */
  
  /* ここでは分割しているだけ */
  mid = (left + right) / 2;       /* 中央の値より */
  MergeSort(x, left, mid,n,p);        /* 左を再帰呼び出し */
  MergeSort(x, mid + 1, right,n,p);   /* 右を再帰呼び出し */
  
  /* x[left] から x[mid] を作業領域にコピー */
  for (i = left; i <= mid; i++){
    temp[i] = x[i];
  }
  
  /* x[mid + 1] から x[right] は逆順にコピー */
  for (i = mid + 1, j = right; i <= right; i++, j--){
    temp[i] = x[j];
  }
  
  i = left;         /* i とj は作業領域のデーターを */
  j = right;        /* k は配列の要素を指している */
  
  for (k = left; k <= right; k++){    /* 小さい方から配列に戻す */
    if (temp[i] <= temp[j]){
      /* ここでソートされる */
      e++;
      x[k] = temp[i++];
    }
    else
      x[k] = temp[j--];   
  }
  
  *p=e;
}


void main(void)
{
  
  int *x;
  int n,i,l;
  scanf("%d",&n);
  x=(int *)malloc( sizeof(int)*n);
  
  for(i=0;i<n;i++){
    scanf("%d",&x[i]);
  }
  
  MergeSort(x,0,n-1,n,&l);
  
  /* ソート後のデータを表示 */
  for (i = 0; i < n; i++){
    printf("%d", x[i]);
    if(i==n-1)
      printf("\n");
    else
      printf(" ");
  }
  
  printf("%d\n",l);
  free(x);
}

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

+1

こんにちは。
  *p=e; 

ここで、最後の再帰マージ時の比較回数で上書きしているからでは?
加算してやらないといけないような…。

C言語の理解は浅いですが、ポインタだったら勝手に加算されたりとかするのでしょうか。
であれば私の検討違いです、すみません。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

比較回数をカウントしたいのであれば
    for (k = left; k <= right; k++){    /* 小さい方から配列に戻す */ 
        if (temp[i] <= temp[j]) { 
            /* ここでソートされる */ 
            x[k] = temp[i++]; 
        } else { 
            x[k] = temp[j--];
        }
        e++;  /* 比較回数のカウント */
    } 
とすべきですよね。元の位置でカウントアップしても、これは比較した結果「入れ替えが発生した場合」のカウントしかされていないです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/05/15 12:18

    配列を一つ一つの要素に分ける前も合わせての総合的な比較回数を調べたいんですけど、どうすればいいですか?
    これだとたぶん分けた後のしか数えてないみたいで・・・
    ちなみに実際は13回比較しているんですけど、教えてもらった位置で数えると8回しか数えていません

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.49%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る