目次
はじめに
今回も、応用情報技術者試験の過去問を解いていきます。
応用情報では、プログラム設計やアルゴリズムの理解を問う問題が頻繁に出題されます。
その中でも ソートアルゴリズム（並び替え） は定番テーマです。
この記事では、問題を解くだけでなく
- ソートアルゴリズムとは何か
- ITの世界でどこで使われているのか
- アルゴリズムの体系の中での位置
まで整理して解説します。
問題
整列方法に関するアルゴリズムの記述のうち，バブルソートの記述はどれか。
ここで，整列対象は重複のない1から9の数字がランダムに並んでいる数字列とする。
ア
数字列の最後の数字から最初の数字に向かって，隣り合う二つの数字を比較して小さい数字が前に来るよう数字を入れ替える操作を繰り返し行う。
イ
数字列の中からランダムに基準となる数を選び，基準より小さい数と大きい数の二つのグループに分け，それぞれのグループ内も同じ操作を繰り返し行う。
ウ
数字列をほぼ同じ長さの二つの数字列のグループに分割していき，分割できなくなった時点から，グループ内で数字が小さい順に並べる操作を繰り返し行う。
エ
未処理の数字列の中から最小値を探索し，未処理の数字列の最初の数字と入れ替える操作を繰り返し行う。
解答
ア
解説
この問題は 代表的なソートアルゴリズムの特徴を理解しているかを問う問題です。
各選択肢は次のアルゴリズムを説明しています。
| 選択肢 | アルゴリズム |
|---|---|
| ア | バブルソート |
| イ | クイックソート |
| ウ | マージソート |
| エ | 選択ソート |
バブルソート（正解）
バブルソートは
隣り合う要素を比較しながら交換するアルゴリズム
です。
動きのイメージ
5 3 8 2
↓
3 5 8 2
↓
3 5 2 8
↓
3 2 5 8
↓
2 3 5 8
大きい数字が右端へ移動していく様子が
泡（bubble）が水面に浮かぶように見えることから
Bubble Sort
という名前がついています。
イ：クイックソート
クイックソートは
基準値（pivot）を決めてデータを分割するアルゴリズム
です。
8 3 5 1 7
pivot = 5
小さいグループ
3 1
大きいグループ
8 7
この処理を再帰的に繰り返します。
平均計算量
| 計算量 |
|---|
| O(n log n) |
ウ：マージソート
マージソートは
データを分割して最後に結合するアルゴリズム
です。
8 3 5 1↓ 分割8 3 | 5 1↓ 分割8 | 3 | 5 | 1↓ マージ3 8 | 1 5↓ マージ1 3 5 8
エ：選択ソート
選択ソートは
毎回最小値を選んで先頭と交換するアルゴリズム
です。
4 7 2 1最小値 1
↓
1 7 2 4最小値 2
↓
1 2 7 4
問題の用語解説
ソート（Sort）
ソートとは
データを一定の順序に並び替える処理
です。
例
5 2 8 1
↓
1 2 5 8
ITシステムでは非常に多く使われます。
ソートアルゴリズム比較
| アルゴリズム | 平均計算量 | 特徴 |
|---|---|---|
| バブルソート | O(n²) | 隣接交換 |
| 選択ソート | O(n²) | 最小値探索 |
| 挿入ソート | O(n²) | 挿入 |
| クイックソート | O(n log n) | 分割 |
| マージソート | O(n log n) | 分割＋結合 |
体系的位置づけ
アルゴリズムは次のような体系で整理できます。
アルゴリズム
│
├─ ソート
│ ├─ バブルソート
│ ├─ 選択ソート
│ ├─ クイックソート
│ └─ マージソート
│
└─ 探索
├─ 線形探索
└─ 二分探索
さらにアルゴリズムは
設計技法でも分類されます。
アルゴリズム設計技法
│
├─ 全探索
├─ 分割統治
├─ 動的計画法
└─ 貪欲法
この中で
| アルゴリズム | 設計技法 |
|---|---|
| クイックソート | 分割統治 |
| マージソート | 分割統治 |
| 二分探索 | 分割統治 |
となります。
ITの世界でどこで使われているのか
ソートはITシステムの多くの場所で使われています。
データベース
SQLの
ORDER BY
は内部でソートを行います。
例
SELECT * FROM users
ORDER BY age;
検索エンジン
検索結果は
スコア計算
↓
スコア順にソート
↓
結果表示
という処理になっています。
ECサイト
ECサイトでは
- 売上ランキング
- 人気順
- レビュー順
などでソートが使われています。
Excelなどのツール
Excelの
データ → 並べ替え
もソートアルゴリズムです。
まとめ
今回の問題では
ソートアルゴリズムの特徴を理解しているか
が問われています。
ポイントは次の通りです。
| キーワード | アルゴリズム |
|---|---|
| 隣接比較 | バブルソート |
| 基準値 | クイックソート |
| 分割 | マージソート |
| 最小値探索 | 選択ソート |
ソートは
- データベース
- 検索エンジン
- ECサイト
- データ分析
など、ITの多くの分野で使われる重要なアルゴリズムです。
応用情報では頻出テーマなので、
アルゴリズムの特徴と計算量をセットで覚えることが重要です。
- IPA 独立法人 情報処理推進機構 応用情報技術者試験 過去問 https://www.ipa.go.jp/shiken/mondai-kaiotu/index.html
コメント