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

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

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

再帰処理を使ったマージソートについて

[トピック内 8 記事 (1 - 8 表示)]  << 0 >>

■83620 / inTopicNo.1)  再帰処理を使ったマージソートについて
  
□投稿者/ souya (1回)-(2017/03/30(Thu) 22:00:14)

分類:[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);
となっております。

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

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





引用返信 編集キー/
■83621 / inTopicNo.2)  Re[1]: 再帰処理を使ったマージソートについて
□投稿者/ もりお (34回)-(2017/03/31(Fri) 00:41:54)
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


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

引用返信 編集キー/
■83623 / inTopicNo.3)  Re[1]: 再帰処理を使ったマージソートについて
□投稿者/ shu (994回)-(2017/03/31(Fri) 09:00:46)
No83620 (souya さん) に返信

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

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

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


引用返信 編集キー/
■83625 / inTopicNo.4)  Re[2]: 再帰処理を使ったマージソートについて
□投稿者/ souya (2回)-(2017/03/31(Fri) 10:35:23)
みなさん、回答ありがとうございます。
マージソートの前に再帰処理について、ちょっと分からない事が
あるので、追記で質問させてください

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

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になるのか分かりません

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



引用返信 編集キー/
■83626 / inTopicNo.5)  Re[3]: 再帰処理を使ったマージソートについて
□投稿者/ shu (995回)-(2017/03/31(Fri) 11:07:39)
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となります。


 

引用返信 編集キー/
■83631 / inTopicNo.6)  Re[4]: 再帰処理を使ったマージソートについて
□投稿者/ 774RR (503回)-(2017/03/31(Fri) 11:45:49)
再帰の際にローカル変数は同じ名前であっても別物である、ってことで。

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

引用返信 編集キー/
■83634 / inTopicNo.7)  Re[3]: 再帰処理を使ったマージソートについて
□投稿者/ 魔界の仮面弁士 (1230回)-(2017/03/31(Fri) 12:52:44)
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 からの最初の呼び出しが完了。
引用返信 編集キー/
■83660 / inTopicNo.8)  Re[4]: 再帰処理を使ったマージソートについて
□投稿者/ souya (4回)-(2017/04/01(Sat) 01:21:26)
おかげさまで、再帰処理の流れと
マージソートの流れを理解する事ができました。

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

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


解決済み
引用返信 編集キー/

このトピックをツリーで一括表示


トピック内ページ移動 / << 0 >>

このトピックに書きこむ