基本情報技術者試験、令和5年、科目B、問3の問題です。 問３ 次の記述中の□ に入れる正しい答えを，解答群の中から…

Question

基本情報技術者試験、令和5年、科目B、問3の問題です。

問３ 次の記述中の□ に入れる正しい答えを，解答群の中から選べ。ここで，
配列の要素番号は 1 から始まる。次の手続 sort は，大域の整数型の配列 data の，引数 first で与えられた要素番号
から引数 last で与えられた要素番号までの要素を昇順に整列する。ここで，first
＜ last とする。手続 sort を sort(1, 5) として呼び出すと，/*** α ***/ の行を最
初に実行したときの出力は“□ ”となる。

〔プログラム〕
大域: 整数型の配列: data ← {2, 1, 3, 5, 4}
○sort(整数型: first, 整数型: last)
整数型: pivot, i, j
pivot ← data[(first ＋ last) ÷ 2 の商]
i ← first
j ← last
while (true)
while (data[i] ＜ pivot)
i ← i ＋ 1
endwhile
while (pivot ＜ data[j])
j ← j － 1
endwhile
if (i ≧ j)
繰返し処理を終了する
endif
data[i]とdata[j]の値を入れ替える
i ← i ＋ 1
j ← j － 1
endwhile
dataの全要素の値を要素番号の順に空白区切りで出力する /*** α ***/
if (first ＜ i － 1)
sort(first, i － 1)
endif
if (j ＋ 1 ＜ last)
sort(j ＋ 1, last)
endif

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

答えはエとなります。

以下、私の分からない部分になります。

そもそもの問題の、
「次の手続 sort は，大域の整数型の配列 data の，引数 first で与えられた要素番号
から引数 last で与えられた要素番号までの要素を昇順に整列する。ここで，first
＜ last とする。」の意味がよく分かりません。
「要素番号の要素を昇順」という言葉は、要素番号を昇順にすることを意味するのか、中身を昇順にすることを意味するのか、イマイチよく分かりません。
要素番号を昇順にするもなにも、そもそも要素番号は昇順になっているのでは？と考えてしまいます。

それが故、以下の
「dataの全要素の値を要素番号の順に空白区切りで出力する /*** α ***/」の意味もよく分かりません。元々要素番号は昇順になっているので、そのまま区切ればいいだけなのでは？と、、、

全くの無知で申し訳ありません。お恥ずかしい限りではございますが、この「要素番号の要素を昇順」という言葉の正体を教えてください、、、

Answer 1

>基本情報技術者試験、令和5年、科目B、問3
勉強の仕方が間違ってます。

あなたが見ているやつはあくまで試験のための対策本であり、アルゴリズムを勉強するには向いてません。穴埋めしつつ問題解きながら新しいアルゴリズムをお勉強するのは、その本では無理です。

「C言語によるデータ構造とアルゴリズム」などとされている本を見ると、全てのコードが開示されている状態で勉強できますので、そのような本を買います。つまり勉強するにあたっての無駄な穴埋めや問題化が無いので、スムーズに理解可能です。

このアルゴリズムが正式にはどういう名前が付けられているか知らないままこの試験を受けようとするのは非常に無謀です。

「要素番号の要素を昇順」という点については至極一般的な配列を用いたソートですので深く考える要素ではないです。さらに正しくは「要素番号までの要素を昇順に整列」です。「長さ５だけれども、１番目から３番目までの要素だけを並べ替える」などという意味になることがこのソートの教科書的な説明には出てくるので、最初にアルゴリズムの本を読んだ方がいいです。つまり「全部ではなく部分的に（配列を）並べ替えろ」という文芸的意味です。

何故部分的かと言うと、これがこのクイックソートのアルゴリズムだからです。なので教科書を買ってついでに説明動画を見るとクイックソートがどのように動いているのかを直感できます。

つまり、根本的には勉強の仕方が間違ってます。問題を解きながら勉強するのは無理です。

Answer 2

「要素番号の要素を昇順」 = 「"要素番号に該当する要素"を昇順」にするという意味です。

「常識的に考えて、要素番号を昇順に並び替えるような意味のわからない問題は出さないだろう」と考えられるでしょうし、処理の内容を見たら要素を並び替えているのが読み取れるので、「"要素番号の要素を昇順"は"要素を昇順にする"という意味だな」と考えることができると思います。

Answer 3

その問題で考えるのではなく、「クイックソート」でググって出てきた解説サイトを読みましょう。