整列アルゴリズムの試験問題への適用
整列の試験問題では、途中配列・比較回数・確定位置を問われる。各アルゴリズムの1回の処理単位を明確にして追う。
この単元で学ぶこと
- バブル1走査の意味と役割を説明できる
- 選択1回の意味と役割を説明できる
- 挿入1回の意味と役割を説明できる
- 各整列方式の途中状態と比較/交換回数を区別して求められる
本文解説
バブルは1走査、選択は1回の最小値配置、挿入は1要素の挿入を単位にする。問題文の「1回」がどの単位かを確認する。
バブル1走査 隣接比較を端まで行い一つの端要素を確定する。 昇順なら最大値が右端へ移る実装が典型。
選択1回 未整列範囲から最小を見つけ先頭と交換する。 未整列範囲が1つ縮む。
挿入1回 次要素を整列済み部分の適切位置へ入れる。 必要な要素を右へずらす。
比較回数 キー同士を比較した回数。 交換回数とは別。
交換回数 実際に二要素の位置を入れ替えた回数。 比較回数より少ないことがある。
問題文の1ステップ定義を確認し、比較と交換を別カウントする。
[1,2,3]のバブル1走査では比較は2回でも交換は0回。
図解
重要ポイント
- バブル1走査: 隣接比較を端まで行い一つの端要素を確定する。
- 選択1回: 未整列範囲から最小を見つけ先頭と交換する。
- 挿入1回: 次要素を整列済み部分の適切位置へ入れる。
- 比較回数: キー同士を比較した回数。
- 比較した回数と交換した回数は同じとは限らない。
間違えやすい点
- 1回=全体終了と決めつけない。
- 比較回数を交換回数として数えない。
- 既に整列済みでも比較が発生する実装を見落とさない。
用語解説
- バブル1走査
- 隣接比較を端まで行い一つの端要素を確定する。
- 選択1回
- 未整列範囲から最小を見つけ先頭と交換する。
- 挿入1回
- 次要素を整列済み部分の適切位置へ入れる。
- 比較回数
- キー同士を比較した回数。
- 交換回数
- 実際に二要素の位置を入れ替えた回数。
関連教材
参考資料
教材データに登録された参考リンクです。リンク先の内容や更新日は提供元でご確認ください。
確認問題の出題・採点や学習履歴の保存にはログインが必要です。