ソートアルゴリズムとは？

詳細解説

ソートアルゴリズム（Sorting Algorithm）は、配列やリストの要素を特定の順序（昇順・降順・辞書順など）に並べ替える処理手順の総称です。FE試験で扱う主なソートアルゴリズムの特性比較は次の通りです。バブルソート：隣接2要素を比較・交換を繰り返す。計算量O(n²)・安定ソート・実装が最もシンプル。選択ソート：未整列部の最小値を選んで先頭と交換を繰り返す。計算量O(n²)・不安定ソート。挿入ソート：未整列の要素を整列済み部分の適切な位置に挿入する。計算量O(n²)だが、ほぼ整列済みなら最良O(n)。安定ソート。クイックソート：ピボットで分割を再帰的に繰り返す分割統治型。平均O(n log n)・最悪O(n²)・不安定ソート。マージソート：再帰的に半分に分割してマージする。最悪でもO(n log n)保証・安定ソート・空間O(n)。ヒープソート：ヒープを使って最大値を繰り返し取り出す。最悪でもO(n log n)・不安定ソート・空間O(1)。安定ソートの代表はバブル・挿入・マージです。FE試験では「各アルゴリズムの計算量と安定性の組み合わせを選ぶ問題」「ソートの途中経過のトレース問題（何回目のパスでどの状態になるか）」が頻出です。内部ソート（データが全てメモリに収まる）と外部ソート（ディスクを使う・マージソートの応用）の区別も覚えておきましょう。

FE試験での出題ポイント

• 1O(n²)ソート：バブル・選択・挿入（シンプルだが大規模データ非推奨）
• 2O(n log n)ソート：クイック（平均）・マージ（最悪保証）・ヒープ
• 3安定ソート：バブル・挿入・マージ。不安定ソート：選択・クイック・ヒープ
• 4途中経過トレース：何回目のパスでどの要素がどこに移動するかを手で追う

関連用語