令和5年度秋期 データベーススペシャリスト 午前Ⅰ 問3

連続する状態の差分に着目する

整列の途中経過が与えられたときは、隣り合う二つの状態を比べて何がどれだけ変化したかを丁寧に記録することが出発点です。変化の範囲や規則性を自分の言葉で整理してから、学習した各手法の手順と照らし合わせましょう。

この問題で問われていること

この問題で問われているのは、ある段階から次の段階へ進む一回の処理で、データ列のどの位置が変化し、どの位置がそのまま残っているかを正確に読み取り、手法の手順と対応づける力です。

視点

整列の手法はどれも、要素どうしの比較と位置の変更を繰り返して並びを整えます。ただし、一回の処理で手が加わる範囲や、処理が進むにつれて並びが整っていく順序は手法ごとに異なります。そのため、最終的な見た目の印象で判断せず、段階ごとの差分を事実として書き出すことが大切です。そのうえで、各手法の手順を最初の状態から自分で一段ずつ動かし、書き出した差分と一致するかを確かめると、根拠を持って判断できます。

確認ポイント

• 隣り合う二つの状態を並べ、位置が変わった要素に印を付けたか
• 各段階で変化した要素の数と位置の範囲を、段階ごとに書き出したか
• 学習した手法の手順を最初の状態から自分で一段ずつ試し、与えられた推移と一致するか確かめたか

正解

ウ

解説

状態0の3、5、9、6、1、2を左から隣同士で比較・交換すると、最大値9が末尾へ移って状態1になり、次の走査で6が移って状態2になる。この推移はバブルソートと一致するので、正答はウだよ。

理由

状態0の3、5、9、6、1、2を左から隣同士で比べると、3と5、5と9はそのまま。9と6を交換して3、5、6、9、1、2、9と1を交換して3、5、6、1、9、2、9と2を交換して3、5、6、1、2、9となり、状態1と一致する。2回目の走査では6と1、6と2を交換して3、5、1、2、6、9となり、状態2と一致する。1回の走査ごとに残りの最大値が末尾側に確定していく、バブルソートの推移だよ。

比較

ヒープソートも最大値を末尾へ移して確定するが、残りの部分を最大ヒープに再構成するため、先頭には残りの最大値が来る。状態0からヒープを作ると9、6、3、5、1、2となり、9を末尾へ移して再構成すると6、5、3、2、1、9になるので、状態1の3、5、6、1、2、9とは合わない。挿入ソートは先頭側の整列済み部分へ次の要素を差し込む方式で、クイックソートは基準値で分割する方式なので、どちらもこの推移にはならないよ。

選択肢ア

これは不正解だよ。クイックソートは基準値を選び、それより小さい値を前へ、大きい値を後ろへ集めるように分割する。例えば先頭の3を基準値にすると、1と2は3より前へ移るはずだ。しかし状態1・2では3,5が先頭のまま、1,2は一つずつ左へずれるだけで、隣接交換によって最大値が末尾へ運ばれる推移になっているよ。

選択肢イ

これは不正解だよ。挿入ソートは先頭側の整列済み部分に次の要素を一つずつ差し込むので、まだ処理していない後ろ側の並びは変わらない。状態0は3,5,9までが整列済みなので、次は6を差し込んで3,5,6,9,1,2になるはずだ。しかし状態1では9が末尾へ移り、1と2も動いているので一致しないよ。

選択肢ウ（正解）

これは正解だよ。状態0の3,5,9,6,1,2を左から隣同士で比べると、9と6、9と1、9と2が順に交換されて状態1の3,5,6,1,2,9になる。次の走査では6と1、6と2が交換されて状態2の3,5,1,2,6,9になる。隣接交換で残りの最大値を末尾へ移していく推移はバブルソートと一致するよ。

選択肢エ

これは不正解だよ。ヒープソートも最大値を末尾へ移して確定するが、残りの部分を最大ヒープに再構成するため、先頭には残りの最大値が来る。状態0からヒープを作ると9,6,3,5,1,2となり、9を末尾へ移して再構成すると6,5,3,2,1,9になる。状態1は先頭が3で、残り5要素の最大値6ではないので一致しないよ。

学習のポイント

途中状態の配列から、隣接交換・挿入・分割・ヒープ再構成の違いを見分けること