応用情報技術者試験に頻出するソートについてまとめました。
ソート
ソートとは
ソートとは、データを一定のルールに従って昇順・降順に並びかえることです。
ただ、並びかえるといっても様々な方法がありますので、次項から代表的なソートを説明していきます。
バブルソート（基本交換法）
バブルソートとは、隣接する要素を比較して並び替えしていく方法です。
要素が小さい（もしくは大きい）ものから浮かび上がるように並び替えされることから、バブル（泡）ソートと呼ばれます。
挿入ソート（基本挿入法）
挿入ソートとは、未整列の要素を含む配列と整列済みの要素を含む配列に分け、
未整列の要素と整列済みの要素を比較し、
未整列の要素が小さければ（もしくは大きい）、整列済みの配列へ挿入していく方法です。
選択ソート（基本選択法）
選択ソートとは、未整列の要素を含む配列と整列済みの要素を含む配列に分け、未整列の要素の中で最も小さい（もしくは大きい）要素を選択し、整列済みの配列へ挿入していく方法です。
マージソート
マージソートは配列を分解していき、１つの要素となるまで分割したら、比較し並べ替えながら配列を併合（マージ）していく方法です。
分割統治法の一つです。
クイックソート
クイックソートは実用上最も高速と言われているソートで、軸要素（配列の先端要素）を決め、軸要素よりも大きいか小さいかで配列を分解していく方法です。
分割統治法の一つです。
ヒープソート
ヒープソートは配列を二分木にし、ヒープ構造（子要素は親要素より常に大きいか等しい）を作成してから、並び替えしていく方法です。
シェルソート
シェルソートは挿入ソートの改良版で、一定間隔で取り出した要素で部分配列を作り並び替えてから挿入ソートをする方法です。
覚えづらいですが、ドナルド・シェル氏が作ったためシェルソートです。
分割統治法
分割統治法とは、問題解決の手段の一つで大きな問題を分割して小さい問題にしていき、簡単に解けるようにする方法です。
ソートする際は配列を分割していくため、コードを書く際は再帰的（関数Aの中で関数A（自分自身）を呼び出すこと）に記述する必要があります。
代表的な方法として、マージソートとクイックソートがあります。
演習問題
実際の試験の過去問を解いてみましょう。
応用情報技術者試験 令和元年秋期 午前問8 問題
| IPA 応用情報技術者試験（AP） 問題より 問8 分割統治を利用した整列法はどれか。 選択肢 ア 基数ソート イ クイックソート ウ 選択ソート エ 挿入ソート |
応用情報技術者試験 令和元年秋期 午前問8 解答
分割統治法とは、問題解決の手段の一つで大きな問題を分割して小さい問題にしていき、簡単に解けるようにする方法です。
代表的な方法として、マージソートとクイックソートがあります。
ア 基数ソート
→桁数毎に並び替えしていくソートです。
分割統治法ではありません。
イ クイックソート
→軸要素を決め、軸要素よりも大きいか小さいかで配列を分解していく方法です。
分割統治法の一つです。
ウ 選択ソート
→未整列の要素を含む配列と整列済みの要素を含む配列に分け、未整列の要素の中で最も小さい（もしくは大きい）要素を選択し、整列済みの配列へ挿入していく方法です。
分割統治法ではありません。
エ 挿入ソート
→未整列の要素を含む配列と整列済みの要素を含む配列に分け、未整列の要素と整列済みの要素を比較し、未整列の要素が小さければ（もしくは大きい）、整列済みの配列へ挿入していく方法です。
分割統治法ではありません。
以上から、答えは「イ」となります。
ソートの解説は以上です。
こちらに他の応用情報技術者試験のまとめについて掲載していますので、
良かったらご覧ください。
当ブログ「応用情報技術者解答解説」まとめページはこちら
