代表的なソートアルゴリズム

ソートアルゴリズムは、キーの昇順・降順等にデータを並べ替える手順で、計算量、追加領域、安定性、入力特性が異なります。

■ 試験で押さえるポイント

• バブル・選択・挿入ソートは平均・最悪$O(n^2)$で、挿入ソートはほぼ整列済みの小規模データに有効です。

• マージソートは分割・統合で常に$O(n\log n)$、安定ですが通常$O(n)$の追加領域が必要です。

• クイックソートは基準値で分割し平均$O(n\log n)$、最悪$O(n^2)$で、一般に高速ですが基準値選択へ注意します。

• ヒープソートは最悪$O(n\log n)$で追加領域を小さくでき、計数ソート等はキー範囲が限定されれば比較ソートの下限を回避できます。

■ 選択肢での判断ポイント

マージは安定・追加領域あり、クイックは平均高速・最悪二乗、ヒープは最悪でも$n\log n$です。安定ソートは同一キーの元の順序を保つと定義します。

例: 部署順に整列済みの社員を年齢で安定ソートすれば、同年齢内の元の部署順を保てます。