基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

令和５年度  基本情報技術者試験 科目 B 公開問題
問3をトレースしてみましたが、答えに行き着きません。問題文を記載して、返信欄にトレースした結果を記載しています。間違っているところを、教えていただけないでしょうか。
問題
次の手続 sort は，大域の整数型の配列 data の，引数 first で与えられた要素番号から引数 last で与えられた要素番号までの要素を昇順に整列する。ここで，first ＜ last とする。手続 sort を sort(1, 5) として呼び出すと，/*** α ***/ の行を最初に実行したときの出力は“ ”となる。
〔プログラム〕
01)    大域: 整数型の配列: data ← {2, 1, 3, 5, 4}
02)    ○sort(整数型: first, 整数型: last)
03)    整数型: pivot, i, j
04)    pivot ← data[(first ＋ last) ÷ 2 の商]
05)    i ← first
06)    j ← last
07)   while (true)
08)     while (data[i] ＜ pivot)
09)          i ← i ＋ 1
10)     endwhile
11)     while (pivot ＜ data[j])
12)          j ← j － 1
13)     endwhile
14)     if (i ≧ j)
15)     繰返し処理を終了する
16)     endif
17)     data[i]とdata[j]の値を入れ替える
18)         i ← i ＋ 1
19)         j ← j － 1
20)   endwhile
21)   dataの全要素の値を要素番号の順に空白区切りで出力する /*** α ***/
22)   if (first ＜ i － 1)
23)        sort(first, i － 1)
24)   endif
25)   if (j ＋ 1 ＜ last)
26)       sort(j ＋ 1, last)
27)   endif

解答群
ア 1 2 3 4 5  イ 1 2 3 5 4
ウ 2 1 3 4 5  エ 2 1 3 5 4

答え エ

字数制限のため、返信欄にトレース結果を記載します。

ここからトレース
04)    pivot ← data[(first ＋ last) ÷ 2 の商]より
          pivot ← 3 「 (2 ＋ 4) ÷ 2 の商 」
05)    i ← first より   i ← 2
06)    j ← last より   j ← 4
07)   while (true)
08)     while (data[i] ＜ pivot) より
         2＜3なので09) の処理を行う。
09)          i ← i ＋ 1 より   i ← 3 「2 ＋ 1」
08)     while (data[i] ＜ pivot) に戻り、3＜3となり成立しないのでここの処理は終了
10)     endwhile
11)     while (pivot ＜ data[j])
         3＜4なので12)の処理を行う。
12)          j ← j － 1より     j ← 3「4 － 1」
11)     while (pivot ＜ data[j])に戻り、3＜3となり成立しないのでここの処理は終了
13)     endwhile
14)     if (i ≧ j)
15)     繰返し処理を終了する より
           3 ≧ 3となり成立するので、繰返し処理を終了
16)     endif
17)     data[i]とdata[j]の値を入れ替える
18)         i ← i ＋ 1 より        i ← 4「 3 ＋ 1」
19)         j ← j － 1 より        j ← 2「 3 － 1」
20)   endwhile
21)   dataの全要素の値を要素番号の順に空白区切りで出力する /*** α ***/

21)は、ここでなにかするのか、それとも 22)～27)を実行するとことを言っているのか。

22)   if (first ＜ i － 1) より       2＜3「4 － 1」となり成立するので
23)        sort(first, i － 1)  より     sort(2, 3)となり終了
24)   endif
25)   if (j ＋ 1 ＜ last) より  (3「2＋ 1」＜ 4)となり成立するので
26)       sort(j ＋ 1, last) より   sort(3, 4)となり終了
27)   endif

以上、よくわからない結果になってしまいました。よろしくお願いします。

最初が間違っています。

＞04)    pivot ← data[(first ＋ last) ÷ 2 の商]より
          pivot ← 3 「 (2 ＋ 4) ÷ 2 の商 」
05)    i ← first より   i ← 2
06)    j ← last より   j ← 4

>次の手続 sort は，大域の整数型の配列 data の，引数 first で与えられた要素番号から引数 last で与えられた要素番号までの要素を昇順に整列する。

とあるので、sort(1,5)は配列dataを要素番号1から5までを昇順に整列せよ。ということです。

この投稿は投稿者により削除されました。(2023.07.19 23:26)

開始はsort(1,5)で呼び出されます。
01)    大域: 整数型の配列: data ← {2, 1, 3, 5, 4}

解釈が間違っている所を記載いたします。

02)    ○sort(整数型: first, 整数型: last)
first＝1、last＝5となります。
そして
今後firstとした場合は1となり、data[first]とした場合はインデックス1が指している、値2となります。
今後lastとした場合は5となり、data[last]とした場合はインデックス5が指している、値4となります。

04)    (first+last)/2とした場合、上記より(1+5)/2の計算結果3となり、data[3]を指すことにります。参照値は間違ってましたが結果はたまたま一緒です。
05)    firstとしているだけなので1となります。
06)    lastとしているだけなので5となります。

15)    3 ≧ 3となり成立するので、繰返し処理を終了
→繰り返しを終了しているので、この行を囲っているループブロックは破壊され(20)まで飛び(21)からスタートします。
つまり(17)から(19)の交換は行われません。

21)は、現在のdataはどうなってますか？と聞いているので(22)から(27)とは別の処理となってます。

22から24)  firstとしているだけなので1となります。
クイックソートの前半分離部分の再帰処理
25から27)  lastとしているだけなので5となります。
クイックソートの後半分離部分の再帰処理

ループの注意１  ※※※※※※※※※※※※※※※※※※※※※

ループが重なっている場合は以下となります。
while()  ①
＿while()  ②
＿＿if()
＿＿＿ループを終了する  ここで破壊するのはこの行を囲っている②ループになります。
＿＿＿そのため②の継続処理は破壊と同時に消滅しますが
＿＿＿①のループ処理生き残っているので、①の継続処理も合わせて生きてます。
＿＿＿なのでこの場合ループを終了するの次の処理は、①の継続処理となります。
＿＿②の継続処理
＿endwhile
＿①の継続処理
endwhile
③ループ外の処理

ループの注意２  ※※※※※※※※※※※※※※※※※※※※※

while()  ①
＿if()
＿＿ループを終了する  この場合どこから処理は開始されますか？
＿while()  ②
＿＿②の継続処理
＿endwhile
＿①の継続処理
endwhile
③ループ外の処理

ああｗ、まーぼ先生が書いてくれてるので私のは最後のループの注意部分以外飛ばしてもらってもいいです

pivot ＝  data[(1+5)/2の商] = data[3] = 3


i = 1


j = 5


07) while(true)のループに入る
08)data[1] = 2,pivot=3なのでwhile (data[i] ＜ pivot) のループに入る
09)iを1増加させてi=2

08)data[2] = 1,pivot=3なのでwhile (data[i] ＜ pivot) のループを続ける
09)iを1増加させてi=3

08)data[3] = 3,pivot=3なのでwhile (data[i] ＜ pivot) のループを抜ける

11)data[5] = 4,pivot =3なのでwhile (pivot ＜ data[j])のループに入る
12)jを1減少させる

11)data[4] = 5,pivot = 3なのでwhile (pivot ＜ data[j])のループを続ける
12)jを1減少させる

11)data[3] = 3,pivot = 3なのでwhile (pivot ＜ data[j])のループを抜ける


ここは正しいです。一番内側の繰り返し処理（while(true)のループ）を抜けます。


17～20はwhile(true)のループの中に記述されていて、このループは抜けたので実行されません。


dataの中身を出力せよということです。dataの入れ替えを行わず、ループを抜けたので最初のdataと同じで

2 1 3 5 4と出力されます。

まーぼさん、電タックさん、丁寧な解説のご返信ありがとうございます。当方のポンコツPCから煙が…理解にもう少し時間がかかりそうです。

ちなみに、このプログラムは、実行すると{2,?1,?3,?5,?4}を{1,?2, 3,?4, 5}にソートするものであるが、この問への回答としては、単に

21)???dataの全要素の値を要素番号の順に空白区切りで出力する?/***?α?***/

だけをみて答えれば良い。
ということなのでしょうか…？

(要素の値とか要素番号という言葉がスッと入ってきませんが、要素番号は、配列の順番のことなので、要素番号１の値は2ということですよね…)

 よろしくお願いします。

>tkさん


結果としてたまたま並び変える前の配列と同じ並びになっただけなので、21行目以外も見る必要があります。

問題に

>手続 sort を sort(1, 5) として呼び出すと，/*** α ***/ の行を最初に実行したときの出力は“ ”となる。

とあるので、行αを最初に実行したときの出力を求める問題です。最後に行αを実行したときの出力はソート済みになり、
1 2 3 4 5

と出力されます。

要は行αの存在意義は、並び変えの様子を出力するためにあります。


要素の値とはdata[1]やdata[3]のことで
要素番号は上の[]の中の数字です。

data = {2,1,3,5,4}のとき、

>dataの全要素の値を要素番号の順に空白区切りで出力する

全要素とは{}の中の数字のことです。
これを要素番号の順に出力するので、

data[1] data[2] data[3] data[4] data[5]

という風に出力しますので、

2,1,3,5,4

と出力されます。

https://www.fe-siken.com/s/bbs/4939.html

こちらのNo.6以降でこの問題の解説を書いています。
後に訂正や補足などがあるので最後まで見てください。

まーぼさん、早速ありがとうございます。
最初に処理した結果を出すということが理解できてませんでした。(一事が万事こんな感じですが…)

また、提示されたリンク先で既に解説していただいてましたのですね、気づきませんでした。
お陰様で、この問題のイメージはつかめました。
ブンアイのクイックソートの動画は何回か見ていたのにこの問題とイメージがリンクしなかったです。別の類似の問題がでたら次は大丈夫なのでしょうか…
改めて、トレースし直してみたいと懐います、色々ありがとうございました。

今回は1回目の出力でしたが、応用して2回目の出力、3回目の出力…なども答えられれば十分だと思います。

じゃ結局これって2回目からどうするの？
永久ループにならない？

処理を進めていくと22,25行目のif文の条件が偽になり、再帰呼び出しが行われず終了するようになります。

pivot未満のグループとpivot以上のグループの２つに分割して行き、要素数が1のグループになった場合はそのグループはそれ以上分割されません。

解答ありがとうございました。
この場合は最後まで21354のままな気がして

sort(1,2)

first = 1
last = 2

pivot = data[1] = 2

i = 1,j = 2

8,11行目のwhileの条件式はどちらも偽になり、i,jはそのままです。

14行目の条件式も偽になり、繰り返し処理は終了しない。

17行目でdata[1]とdata[2]を入れ替えます。

18, 19行目でi=2,j=1に更新されます。

while(true)のループを続けます。

8,11行目のwhileの条件式はどちらも偽になり、i,jはそのままです。

14行目の条件式はi=2,j=1なので真になり、while(true)のループを抜けます。

22行目 first = 1,i-1=1のため偽となり実行されません。

25行目 last = 2,j+1=2のため偽となり実行されません。

sort(1,2)はここで終了し、呼び出し元のsort(1,5)の続き（sort(4,5)の呼び出し）から行います。

sort(4,5)が終了すればsort(1,5)の実行は完了します。

data ={1,2,3,5,4}でsort(4,5)を実行したときはご自身でやってみてください。

おそらく基本情報技術者試験だと永久ループする場合は問題文に書いてあると思います。書いてないのに永久ループする場合はどこかでトレースが間違っている可能性が高いです。