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

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

掲示板トップ C# と VB.NET 入門 新規作成 利用方法 ツリー表示 トピック表示 ランキング 記事検索 過去ログ
ログ内検索
  • キーワードを複数指定する場合は 半角スペース で区切ってください。
  • 検索条件は、(AND)=[A かつ B] (OR)=[A または B] となっています。
  • [返信]をクリックすると返信ページへ移動します。
キーワード/ 検索条件 /
検索範囲/ 強調表示/ ON (自動リンクOFF)
結果表示件数/ 記事No検索/ ON
大文字と小文字を区別する

No.83620 の関連記事表示

<< 0 >>
■83620 　再帰処理を使ったマージソートについて
□投稿者/ souya -(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);
    となっております。

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

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




親記事 /過去ログ143より / 関連記事表示
削除チェック/

■83621 　Re[1]: 再帰処理を使ったマージソートについて
□投稿者/ もりお -(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


    図を描くのに全体力を使い果たしましたので説明は割愛ということで(ぇ
記事No.83620 のレス /過去ログ143より / 関連記事表示
削除チェック/

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

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

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

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

記事No.83620 のレス /過去ログ143より / 関連記事表示
削除チェック/

■83625 　Re[2]: 再帰処理を使ったマージソートについて
□投稿者/ souya -(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になるのか分かりません

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


記事No.83620 のレス /過去ログ143より / 関連記事表示
削除チェック/

■83626 　Re[3]: 再帰処理を使ったマージソートについて
□投稿者/ shu -(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となります。
記事No.83620 のレス /過去ログ143より / 関連記事表示
削除チェック/

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

    Sort(0, 7) １段目が２段目を呼ぶ Sort(0, 3) と Sort(4, 7)
    １段目の low と２段目の low は別変数なのでお互いに影響を受けない
    ２段目の low=0 high=3 あるいは low=4 high=7
    ２段目から１段目に戻ってきたとき、１段目の low=0 high=7
記事No.83620 のレス /過去ログ143より / 関連記事表示
削除チェック/

■83634 　Re[3]: 再帰処理を使ったマージソートについて
□投稿者/ 魔界の仮面弁士 -(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 からの最初の呼び出しが完了。
記事No.83620 のレス /過去ログ143より / 関連記事表示
削除チェック/

■83660 　Re[4]: 再帰処理を使ったマージソートについて
□投稿者/ souya -(2017/04/01(Sat) 01:21:26)
    おかげさまで、再帰処理の流れと
    マージソートの流れを理解する事ができました。

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

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

記事No.83620 のレス / END /過去ログ143より / 関連記事表示
削除チェック/



<< 0 >>
パスワード/

- Child Tree -