応用情報技術者試験 令和5年度 秋期 午前 問6
あるデータ列を整列したら状態 0 から順に状態 1、2、・・・、N へと推移した。整列に使ったアルゴリズムはどれか。
状態 0 3, 5, 9, 6, 1, 2 状態 1 3, 5, 6, 1, 2, 9 状態 2 3, 5, 1, 2, 6, 9 ・ ・ ・ 状態 N 1, 2, 3, 5, 6, 9
選択肢を押すと答え合わせができます。
正解と解説を見る
【正解】ウ
バブルソートは、隣り合う要素を順番に比較し、大小関係が逆なら交換する操作を繰り返す整列方法です。昇順に整列する場合、左から右へ1回走査すると、その範囲で最も大きい値が右端まで移動します。
状態0を左から確認すると、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と一致します。次の走査でも同様に、未整列部分の最大値6が右端へ移動し、「3、5、1、2、6、9」という状態2になります。したがって、使用されたのはバブルソートです。
アのクイックソートは誤りです。これは、基準値であるピボットを選び、それより小さい要素と大きい要素に分割して再帰的に整列する方法です。
イの挿入ソートは誤りです。これは、整列済み部分の適切な位置へ、未整列部分から取り出した要素を挿入していく方法です。
エのヒープソートは誤りです。これは、ヒープと呼ばれる木構造を作り、最大値又は最小値を順次取り出して整列する方法です。
【ポイント】 バブルソートでは、1回の走査ごとに未整列部分の最大値が末尾に確定します。 途中状態から整列法を判断するときは、「どの位置の要素が各回で確定しているか」に注目します。
出典：令和5年度 秋期 応用情報技術者試験 午前 問6
※ 解説は SkillStack 編集部が作成したものです。Web 表示のため、図表の配置や表記を一部改めています。
この回の80問を、アプリで通しで解く
- 本番と同じ問題数・制限時間で通し演習（模試モード）
- 間違えた問題は自動で「復習すべき問題」に回る
- 解説で分からない点はAIに質問できる