22年春 基本情報処理試験 問8 マージソート

質問

22年春の基本情報処理試験 、問8のマージソートが解らないでいます。

設問2で与えられている、3、8、2、7、5、1という値を関数Sortに渡し、
これを実行すると、
一番最初に関数Mergeが実行される時に、関数Mergeに渡される引数は、
slist1 = 8、num1 = 1、slist2 = 2、num2 = 1になりますよね？

それで、関数Mergeを実行して、list[] = {2,8} が返却されるところまでは、
理解できるのですが、その後の動きがわかりません。
僕はいくら考えても、ここで終わっちゃうんです。

どの関数に、どの引数を渡してあげればよいのでしょうか…

どなたか教えて下さい。
よろしくお願いします。

回答No.4

Idler999 · ベストアンサー

No.２の者です。

皆さん力作の回答で・・凄い。

Merge関数の中で代入されるのはlist[]引数だけなので、問題的には
ぶっちゃけSlist1[]やSlist2[]が値渡しだろうと参照渡しだろうと関係ありません。

ただ問題の書き方から推測すると参照渡しなんでしょうね。
Sort関数の中で、変数宣言(領域確保)されたものをMerge関数の中で参照しているのでしょう。

Sort関数の冒頭で変数の宣言をしていますね。
i,num1,num2
slist1[]、slist2[]
これらはSort関数が呼ばれる度に新たに領域が確保されます。　←ここ重要

Sort関数
　　変数宣言：slist1[],slist2[]　→Ａ
　　・
　　・
　　Sort関数呼出
　　　　変数宣言：slist1[],slist2[]　→Ｂ
　　　　・
　　　　・
　　end
　　Sort関数呼出
　　　　変数宣言：slist1[],slist2[]　→Ｃ
　　　　・
　　　　・
　　end
　　Merge関数呼出
end

変数の名前は同じですが、Ａのslist1とＢのslist1とＣのslist1は別モノです。

No.１の方へのお礼の中で、
＞再帰2回目]のSort2の直後に戻った時点で、
＞slist1[]の値が、8から3になってますよね。
＞流れ上、slist1[]は、一階層上の、3になってほしいわけですが、
＞こういう場合その辺の管理をどうすればいいのでしょうか？？

とありますが、「1階層上のslist1」は、上記でいうとＡのslist1です。
そこにはずっと「3」が入っています。
下層（ＢやＣ）で、新たに宣言されたslist1に何を入れようが、メモリ上別の領域なので
Ａのslist1には関係ありません。
Ｃのslist1には「8」が入っていた。でもＣのSort関数が終わって戻ってきたとき
（Merge関数を呼び出す時）のslist1は、Ａのslist1、つまり中身は「3」なわけです。

お礼

返信が遅れてしまいすいません。
回答をありがとうございます。

理解できました。

ありがとうございました。

回答No.3

jjon-com

>関数Mergeのその他の引数は値渡しなのでしょうか？

num1, num2は値渡し，
slist1[], slist2[], list[]は参照渡しでしょう。

もしも slist1[], slist2[] が値渡し，すなわち「配列そのもの」を渡しているとするなら，slist1.length のように配列そのものから自身の要素数を知ることができる仕組みを持っているべきだと思いますから。参照渡し（配列の先頭アドレスを渡す）ではそれができないから，別に要素数 num1 を渡さざるを得ないのでしょう。

----------------------------------------
>[再帰2回目]のSort2の直後に戻った時点で、
>slist1[]の値が、8から3になってますよね。

最初に呼ばれたプログラム Sort()は，全体配列 {3,8,2,7,5,1} を入力引数として受け取って，slist1 と slist2 に二分割しますよね。

　　{3,8,2,7,5,1}
　　　↓
　　配列変数名 list で受取
　　＋―――――――――――――――
　　｜プログラム Sort()
　　｜
　　｜・Sort(slist1{3,8,2})
　　｜・Sort(slist2{7,5,1}) ★
　　｜・Merge(…省略…)
　　＋―――――――――――――――

上記★の中の処理をさらに展開したのがこんな概念図なのですが，

　　slist2{7,5,1}
　　　↓
　　配列変数名 list で受取
　　＋―――――――――――――――
　　｜プログラム Sort()
　　｜
　　｜・Sort(slist1{7})
　　｜・Sort(slist2{5,1})
　　｜・Merge(…省略…)
　　＋―――――――――――――――

・配列 slist2{7,5,1} を ■別の仮引数名 list{7,5,1} として受け取る■
・受け取った配列を二分して作られた slist2{5,1} は
　■外から渡された slist2{7,5,1} とはまったく別に新たに確保された配列■

である点の理解は大丈夫でしたでしょうか？

----------------------------------------
他の回答者にならって，私も概念図を提示してみます。

▼(1)～▼(11) がプログラムSort()を呼び出している箇所を表しています。

list{382751}
　　↓▼(1)
＋――――――――――――――――
｜slist1{382}
｜　　↓▼(2)
｜＋―――――――――――――――
｜｜slist1{3} ▼(3)
｜｜
｜｜slist2{82}
｜｜　　↓▼(4)
｜｜＋――――――――――――――
｜｜｜slist1{8} ▼(5)
｜｜｜slist2{2} ▼(6)
｜｜｜Merge(slist1{8}, slist2{2})
｜｜＋――――――――――――――
｜｜　　↓
｜｜slist2{28}
｜｜
｜｜Merge(slist1{3}, slist2{28})
｜＋―――――――――――――――
｜　　↓
｜slist1{238}
｜
｜slist2{751}
｜　　↓▼(7)
｜＋―――――――――――――――
｜｜slist1{7} ▼(8)
｜｜
｜｜slist2{51}
｜｜　　↓▼(9)
｜｜＋――――――――――――――
｜｜｜slist1{5} ▼(10)
｜｜｜slist2{1} ▼(11)
｜｜｜Merge(slist1{5}, slist2{1})
｜｜＋――――――――――――――
｜｜　　↓
｜｜slist2{15}
｜｜
｜｜Merge(slist1{7}, slist2{15})
｜＋―――――――――――――――
｜　　↓
｜slist2{157}
｜
｜Merge(slist1{238}, slist2{157}
＋――――――――――――――――
　　↓
list{123578}

お礼

返事が遅れてしまいすいません。
ご回答ありがとうございます。

この件、理解できました。

ありがとうございます。

回答No.2

Idler999

受験はしておりませんが、公開されていた問題を見て来ました。
久しぶりに頭の体操をした気が(汗)

文章で書くと判りづらいかもしれませんが・・・。

関数Mergeの最後の引数List[]は参照渡しなんですね。
特にそれには触れてありませんが、そうでないとソートが成立しません。
そこはアルゴリズムを見て理解しろ、ということでしょう。

一番最初にMergeが実行された時、List[]={2,8}になりますが、「返却される」
のではなく、Sort関数の引数でもあるList[]自体を書き換えてます。

1回目sort({382751},6)
　　2回目sort({382},3)　　list1={3} list2={8,2}
　　　　3回目sort({3},1)　※引数1なので実行はされず
　　　　4回目sort({82},2) list1={8} list2={2}
　　　　　　5回目sort({8},1)　※実行されず
　　　　　　6回目sort({2},1)　※実行されず
　　　　　　Merge({8},1,{2},1,List[])・・・ここでのListは4回目Sortの引数{8,2}です。
　　　　　　★ここまで終わった時、4回目Sortの引数（＝2回目SortのList2）は{2,8}に書き換わる
　　　　Merge({3},1,{2,8},2,List[])
　　　　　　　　　　　^^^^
　　　　・
　　　　・
　　　　・
となります。上手く書けませんが判りますでしょうか？

お礼

回答をありがとうございます。

流れは理解できたはずなのですが、まだ疑問が…

>関数Mergeの最後の引数List[]は参照渡しなんですね。

ということですが、関数Mergeのその他の引数は値渡しなのでしょうか？
slist1[]の値を追っていて疑問が生まれました。

回答お待ちしております。

回答No.1

Chronos198

この処理の肝は「再帰処理」です。
Sortの処理中に再度Sortを呼んでいるので、後に呼ばれたSortが終わった時点で前のSortに処理が戻るのです。

便宜的にslist1を渡すSortをSort1、slist2を渡すSortをSort2と記します。
以下が処理の遷移するイメージとなります。

最初のSort開始(並び替え開始)
　list[382751] num=6
　slist1[382] slist2[751]

　Sort1開始[再帰1回目]
　　list[382] num=3
　　slist1[3] slist2[82]

　　Sort1開始[再帰2回目]
　　　list[3] num=1
　　　num=1なので終了
　　Sort1終了[再帰2回目]

　　Sort2開始[再帰2回目]
　　　list[82] num=2
　　　slist1[8] slist2[2]

　　　Sort1開始[再帰3回目]
　　　　list[8] num=1
　　　　num=1なので終了
　　　Sort1終了[再帰3回目]

　　　Sort2開始[再帰3回目]
　　　　list[2] num=1
　　　　num=1なので終了
　　　Sort2終了[再帰3回目]

　　　Marge開始
　　　　slist1[8] slist2[2]
　　　　list[28]　　　←ここまでがわかっているところ。
　　　Marge終了
　　Sort2終了[再帰2回目]　←ここで[再帰2回目]のSort2直後に戻ってきている。

　　Marge開始
　　　slist1[3] slist2[28]
　　　list[238]
　　Marge終了
　Sort1終了[再帰1回目]　←ここで[再帰1回目]のSort1直後に戻ってきている。

　Sort2開始[再帰1回目]
　　list[751] num=3
　　slist1[7] slist2[51]
　　　：
　　(略)
　Sort2終了[再帰1回目]

　Marge開始
　　slist1[238] slist2[157]
　　list[123578]
　Marge終了
最初のSort終了(並び替え完了)

お礼

回答をありがとうございます。

プログラムの動きがよく解りました。

ただ、またひとつ疑問が生まれてしまいました。

[再帰2回目]のSort2の直後に戻った時点で、
slist1[]の値が、8から3になってますよね。

流れ上、slist1[]は、一階層上の、3になってほしいわけですが、
こういう場合その辺の管理をどうすればいいのでしょうか？？

[再帰2回目]のSort2の直後に戻った = slist1[]で管理している数値が違う。
という事なのでしょうけれど、ここが解らないです。