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

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

#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);
}

行動規範の内容に同意します

回答2件

こんにちは。

lang
1  *p=e;

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

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

投稿2015/05/15 03:50

編集2015/05/15 03:53

Tak1wa

総合スコア4791

比較回数をカウントしたいのであれば

lang
1    for (k = left; k <= right; k++){    /* 小さい方から配列に戻す */ 
2        if (temp[i] <= temp[j]) { 
3            /* ここでソートされる */ 
4            x[k] = temp[i++]; 
5        } else { 
6            x[k] = temp[j--];
7        }
8        e++;  /* 比較回数のカウント */
9    }