クイックソートによる配列の整列【基本情報技術者試験 科目B 公開問題】

← 科目Bの公開問題一覧へ戻る

　基本情報技術者試験の科目Bの公開問題を題材に，クイックソートによる配列の整列について学習します。この問題では，基準値（pivot）を使って配列を分割し，左右から要素を探索する処理を確認します。

令和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

【参考】	「流れ図と擬似言語によるプログラミングの基礎まとめ」 「アルゴリズムと計算量の基礎まとめ（クイックソートとは）」

この問題のポイント

　この問題から学べることは，

• クイックソートの基本的な処理
• pivot を基準に配列を分割する方法
• iとjを使って左右から要素を探索する方法
• 繰返し処理を終了する条件の読み取り方
• 再帰的に部分配列を整列する方法

です。特に，i ≧ j が成立すると，その時点で繰返し処理を終了し，その後に書かれている要素の入替え処理は実行されないことを理解しておきましょう。

基本情報技術者試験の学習におすすめの参考書

基本情報技術者試験の合格を目指す方におすすめの参考書です。