マージソートについて

マージソートの要素の比較と交換回数を計測するプログラムを作っているのですが、マージのどの段階が交換処理になるのかが分からず困っています。

マージ処理の実行回数をカウントする配列ｓを設けて処理をカウントする場合、以下のプログラムだとどのタイミングでカウントすればよいでしょうか？　ちなみに配列aは初めに値を割り振った配列で、配列bは別途で用意した作業用配列です。

最後のfor文やif文付近で配列の値を変化させて計測してみたのですが、計算量に合った動きをしてくれませんorz

void merge_sort(int a[], int low, int high){
int mid, i, j, k;

if(low >= high)
return;
mid = (low + high)/2;

merge_sort(a, low, mid);
merge_sort(a, mid+1, high);

for(i = low; i <= mid; i++)
b[i] = a[i];

for(i = mid+1, j=high; i <= high; i++, j--)
b[i] = a[j];

i = low; j = high;
for(k = low; k <= high; k++){
if(b[i] <= b[j]){
a[k] = b [i++];
} else{
a[k] = b[j--];
}
}
}

No.1 回答者： Tacosan 回答日時： 2008/06/30 12:35

う～ん, 確かにマージソートだと「交換する」というイメージではないですね. 課題かなにかなら, 出した人に聞いてみればいいんじゃないでしょうか.

まあ, 「マージ処理の実行回数をカウントする」のになぜ配列が必要なのかもよくわからんけど.

この回答へのお礼

レスありがとう御座います！
学年の違う講義課題だったので聞くに聞けずで。。。(汗
やはり交換ってイメージは考えにくいですよね。　比較の視点からいろいろまた模索してみたいと思います！

お礼日時：2008/06/30 23:47

No.2 回答者： JaritenCat 回答日時： 2008/06/30 22:07

とりあえず、比較の回数だけカウントすればいいんじゃないでしょうか。

if文の前にcount++;とか入れれば、n*log2(n)ぐらいの数値が出ると思いますが。。

この回答へのお礼

レスありがとう御座います！
交換というより比較で考えた方がやはりよさそうですかね。。。orz
if文前でもう一度検討してみたいと思います！

お礼日時：2008/06/30 23:45

No.3 ベストアンサー 回答者： sirn 回答日時： 2008/06/30 22:48

ここまでくると完全に回答になってしまうのですが.........

マージの部分だけを数えると、出力結果がNlogNになります。
for(k = low; k <= high; k++){
//ここで数える
if(b[i] <= b[j]){
a[k] = b [i++];
} else{
a[k] = b[j--];
}
}

この回答へのお礼

レスありがとう御座います！
for文の前とif文前で模索していたのですがif文前でしたか。。。
明日もう一度値を変えて検討してみようと思います！

お礼日時：2008/06/30 23:42