C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[4]: 再帰処理を使ったマージソートについて

分類:[C#]　

2017/03/30(Thu) 22:07:30 編集(投稿者)

public class MargeSortArray
{
　　private static void mergeSortArray(int[] a,int low,int high)
　　{
　　　　if(low >= high) { return; }
　　　　int mid = (low + high) / 2;
　　　　
　　　　mergeSortArray(a, low, mid); //再帰01
　　　　mergeSortArray(a, mid + 1, high); //再帰02

　　　　int[] b = new int[a.Length];
　　　　for(int i = low;i <= mid; i++)
　　　　{
　　　　　　b[i] = a[i];
　　　　}

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

　　　　int ii = low;
　　　　int jj = high;

　　　　for(int k = low;k <= high; k++)
　　　　{
　　　　　　if(b[ii] <= b[jj])
　　　　　　{
　　　　　　　a[k] = b[ii++];
　　　　　　}
　　　　　　else
　　　　　　{
　　　　　　　a[k] = b[jj--];
　　　　　　}
　　　　}
　　}

　　public static void sort(int[] a)
　　{
　　　　mergeSortArray(a, 0, a.Length - 1);
　　}
}

利用する側は
int[] a = new int[] { 55, 13, 3, 45, 74, 87, 46, 30 };
MargeSortArray.sort(a);
となっております。

再帰処理を用いた、マージソートのコードなのですが
このコードをどのように読んでいけばいいのか分からず
困っております。

この再帰処理の部分をどのように読んでいけばいいのでしょうか？
みなさまの知恵をお貸しください

■No83620 (souya さん) に返信

再帰には脱出条件が必ずあります。

> if(low >= high) { return; }

これが再帰の脱出条件です。
この条件が成り立つまで再帰を行います。

再帰で何をやってるかですが

> mergeSortArray(a, low, mid); //再帰01
> mergeSortArray(a, mid + 1, high); //再帰02

この2つで配列を分割しています。

https://www.fastpic.jp/images.php?file=4917100747.png

mergeSortArray(a, low, mid) が赤の矢印
mergeSortArray(a, mid + 1, high) が青の矢印です

> int[] b = new int[a.Length];
から下の処理は分割した配列をマージしています

https://www.fastpic.jp/viewer.php?file=1898762672.png
こんな感じです。下から上に登っていきます。

マージのロジックの詳細は以下の図の通りです
https://www.fastpic.jp/images.php?file=6313946980.png

図を描くのに全体力を使い果たしましたので説明は割愛ということで(ぇ

■No83620 (souya さん) に返信

コードについては説明がついているので
マージソートについて
ソートされた２つの配列を１つの配列にしてソートを行うという
考え方に基づきます。

・２つのソート済配列をソートしながら１つの配列にするには
　各配列の要素を順番に参照していき小さいほうを選択していく。
　選択された方のインデックスを進めるというのを繰り返すことにより行います。

・元の配列を真ん中で２つに分け２つの配列にしますが、この２つの配列は
それぞれソート済ではないのでそれぞれマージソートを行います。
　この分割を繰り返すと１つの要素の配列になるのでそれはソート済と
　することが出来ます。

みなさん、回答ありがとうございます。
マージソートの前に再帰処理について、ちょっと分からない事が
あるので、追記で質問させてください

例えば、上記のコードを順にステップ実行した場合

1回目のmergeSortArray(配列の値,0,7)　//一番最初の呼び出し
2回目のmergeSortArray(配列の値,0,3)　//再帰01
3回目のmergeSortArray(配列の値,0,1)　//再帰01
4回目のmergeSortArray(配列の値,0,0)　//再帰01
return　とされ4回目のmergesortArrayの
呼び出しもとに処理が戻されたときに

highの値が1になります。

実引数で値型の値渡しをしているので
returnされたときは実引数の値は変わらない
という風に学んだのですが

なぜ、4回目のmergeSortArrayでreturnされた時に
highの値が1になるのか分かりません

この理由を教えて下さい。

■No83625 (souya さん) に返信

> 1回目のmergeSortArray(配列の値,0,7)　//一番最初の呼び出し
> 2回目のmergeSortArray(配列の値,0,3)　//再帰01
> 3回目のmergeSortArray(配列の値,0,1)　//再帰01
> 4回目のmergeSortArray(配列の値,0,0)　//再帰01
> return　とされ4回目のmergesortArrayの
> 呼び出しもとに処理が戻されたときに
> 
> highの値が1になります。
> 
> 実引数で値型の値渡しをしているので
> returnされたときは実引数の値は変わらない
> という風に学んだのですが
> 
> なぜ、4回目のmergeSortArrayでreturnされた時に
> highの値が1になるのか分かりません
> 

いろいろ省略して書きます
Sort(0,7)
  Sort(0,3)
    Sort(0,1)
      Sort(0,0)
      Sort(1,1)
    Sort(2,3)
  Sort(4,7)
    Sort(4,5)
      Sort(4,4)
      Sort(5,5)
    Sort(6,7)
    Sort(7,7)

という呼び出しになります。
Sort(0,0)からreturnされた状態というのは
Sort(0,1)から呼ばれたSort(0,0)が終了して
Sort(0,1)の継続処理が動くのでHighは1となります。

再帰の際にローカル変数は同じ名前であっても別物である、ってことで。

Sort(0, 7) １段目が２段目を呼ぶ Sort(0, 3) と Sort(4, 7)
１段目の low と２段目の low は別変数なのでお互いに影響を受けない
２段目の low=0 high=3 あるいは low=4 high=7
２段目から１段目に戻ってきたとき、１段目の low=0 high=7

2017/03/31(Fri) 13:01:17 編集(投稿者)

■No83625 (souya さん) に返信
> 実引数で値型の値渡しをしているので
> returnされたときは実引数の値は変わらない
> という風に学んだのですが

引数 int row や引数 int high は値型の値渡し、
引数 int[] a は、参照型の値渡しですね。

そもそも今回、mergeSortArray の中では
引数 low や high の値を参照することはあっても、書き換えることは無いので
すべてが参照渡しであったとしても、実引数 low や high の値は変わりません。

影響があるのは、参照型である引数 a だけです。

> なぜ、4回目のmergeSortArrayでreturnされた時に
> highの値が1になるのか分かりません

実引数と仮引数をどこかで混同していないでしょうか。
http://www.cc.kyoto-su.ac.jp/~yamada/ap/parameter_argument.html

「1 回目の mergeSortArray 呼び出し」の中の仮引数は、最初から最後まで low = 0, high = 7 のまま
「2 回目の mergeSortArray 呼び出し」の中の仮引数は、最初から最後まで low = 0, high = 3 のまま
「3 回目の mergeSortArray 呼び出し」の中の仮引数は、最初から最後まで low = 0, high = 1 のまま
「4 回目の mergeSortArray 呼び出し」の中の仮引数は、最初から最後まで low = 0, high = 0 のまま　(なにもせずreturn)
「5 回目の mergeSortArray 呼び出し」の中の仮引数は、最初から最後まで low = 1, high = 1 のまま　(なにもせずreturn)
「6 回目の mergeSortArray 呼び出し」の中の仮引数は、最初から最後まで low = 2, high = 3 のまま
「7 回目の mergeSortArray 呼び出し」の中の仮引数は、最初から最後まで low = 2, high = 2 のまま　(なにもせずreturn)
「8 回目の mergeSortArray 呼び出し」の中の仮引数は、最初から最後まで low = 3, high = 3 のまま　(なにもせずreturn)
「9 回目の mergeSortArray 呼び出し」の中の仮引数は、最初から最後まで low = 4, high = 7 のまま
「10回目の mergeSortArray 呼び出し」の中の仮引数は、最初から最後まで low = 4, high = 5 のまま
「11回目の mergeSortArray 呼び出し」の中の仮引数は、最初から最後まで low = 4, high = 4 のまま　(なにもせずreturn)
「12回目の mergeSortArray 呼び出し」の中の仮引数は、最初から最後まで low = 5, high = 5 のまま　(なにもせずreturn)
「13回目の mergeSortArray 呼び出し」の中の仮引数は、最初から最後まで low = 6, high = 7 のまま
「14回目の mergeSortArray 呼び出し」の中の仮引数は、最初から最後まで low = 6, high = 6 のまま　(なにもせずreturn)
「15回目の mergeSortArray 呼び出し」の中の仮引数は、最初から最後まで low = 7, high = 7 のまま　(なにもせずreturn)

void sort からの最初の呼び出しは、実引数　第2引数:0、第3引数:a.Length - 1(=7)

　　「1 回目の mergeSortArray 呼び出し」を開始
　　仮引数　low:0、high:7 を受けて、mid = 3 が算出される

　　「1 回目」における再帰01での呼び出し　第2引数:low(=0)、第3引数:mid(=3)

　　　　「2 回目の mergeSortArray 呼び出し」を開始
　　　　仮引数　low:0、high:3 を受けて、mid = 1 が算出される

　　　　「2 回目」における再帰01での呼び出し　第2引数:low(=0)、第3引数:mid(=1)

　　　　　　「3 回目の mergeSortArray 呼び出し」を開始
　　　　　　仮引数　low:0、high:1 を受けて、mid = 0 が算出される

　　　　　　「3 回目」における再帰01での呼び出し　第2引数:low(=0)、第3引数:mid(=0)

　　　　　　　　「4 回目の mergeSortArray 呼び出し」を開始
　　　　　　　　仮引数　low:0、high:0 を受けて、何もせずに return;
　　　　　　　　「4 回目」が途中で中断されて再帰完了。

　　　　　　「3 回目」における再帰02での呼び出し　第2引数:mid + 1(=1)、第3引数:high(=1)

　　　　　　　　「5 回目の mergeSortArray 呼び出し」を開始
　　　　　　　　仮引数　low:1、high:1 を受けて、何もせずに return;
　　　　　　　　「5 回目」が途中で中断されて再帰完了。

　　　　　　「3 回目」が最後まで実行されて完了。

　　　　「2 回目」における再帰02での呼び出し　第2引数:mid + 1(=2)、第3引数:high(=3)

　　　　　　「6 回目の mergeSortArray 呼び出し」を開始
　　　　　　仮引数　low:2、high:3 を受けて、mid = 2 が算出される

　　　　　　「6 回目」における再帰01での呼び出し　第2引数:low(=2)、第3引数:mid(=2)

　　　　　　　　「7 回目の mergeSortArray 呼び出し」を開始
　　　　　　　　仮引数　low:2、high:2 を受けて、何もせずに return;
　　　　　　　　「7 回目」が途中で中断されて再帰完了。

　　　　　　「6 回目」における再帰02での呼び出し　第2引数:mid + 1(=3)、第3引数:high(=3)

　　　　　　　　「8 回目の mergeSortArray 呼び出し」を開始
　　　　　　　　仮引数　low:3、high:3 を受けて、何もせずに return;
　　　　　　　　「8 回目」が途中で中断されて再帰完了。

　　　　　　「6 回目」が最後まで実行されて完了。

　　　　「2 回目」が最後まで実行されて完了。

　　「1 回目」における再帰02での呼び出し　第2引数:mid + 1(=4)、第3引数:high(=7)

　　　　「9 回目の mergeSortArray 呼び出し」を開始
　　　　仮引数　low:4、high:7 を受けて、mid = 5 が算出される

　　　　「9 回目」における再帰01での呼び出し　第2引数:low(=4)、第3引数:mid(=5)

　　　　　　「10 回目の mergeSortArray 呼び出し」を開始
　　　　　　仮引数　low:4、high:5 を受けて、mid = 4 が算出される

　　　　　　「10 回目」における再帰01での呼び出し　第2引数:low(=4)、第3引数:mid(=4)

　　　　　　　　「11 回目の mergeSortArray 呼び出し」を開始
　　　　　　　　仮引数　low:4、high:4 を受けて、何もせずに return;
　　　　　　　　「11 回目」が途中で中断されて再帰完了。

　　　　　　「10 回目」における再帰02での呼び出し　第2引数:mid + 1(=5)、第3引数:high(=5)

　　　　　　　　「12 回目の mergeSortArray 呼び出し」を開始
　　　　　　　　仮引数　low:5、high:5 を受けて、何もせずに return;
　　　　　　　　「12 回目」が途中で中断されて再帰完了。

　　　　「9 回目」における再帰02での呼び出し　第2引数:mid + 1(=6)、第3引数:high(=7)

　　　　　　「13 回目の mergeSortArray 呼び出し」を開始
　　　　　　仮引数　low:6、high:7 を受けて、mid = 6 が算出される

　　　　　　「13 回目」における再帰01での呼び出し　第2引数:low(=6)、第3引数:mid(=6)

　　　　　　　　「14 回目の mergeSortArray 呼び出し」を開始
　　　　　　　　仮引数　low:6、high:6 を受けて、何もせずに return;
　　　　　　　　「14 回目」が途中で中断されて再帰完了。

　　　　　　「13 回目」における再帰02での呼び出し　第2引数:mid + 1(=7)、第3引数:high(=7)

　　　　　　　　「15 回目の mergeSortArray 呼び出し」を開始
　　　　　　　　仮引数　low:7、high:7 を受けて、何もせずに return;
　　　　　　　　「15 回目」が途中で中断されて再帰完了。

　　　　「9 回目」が最後まで実行されて完了。

　　「1 回目」が最後まで実行されて完了。

void sort からの最初の呼び出しが完了。

おかげさまで、再帰処理の流れと
マージソートの流れを理解する事ができました。

とりあえず、再帰処理を用いたソートプログラムは
読めるようになりました。

回答してくださったみなさま、ありがとうございます。

C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[4]: 再帰処理を使ったマージソートについて

過去ログには書き込み不可