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

ソートアルゴリズムは、データを決まった順に並べ替える手順です。方法によって、計算量、必要な追加の記憶領域、安定かどうかが異なります。

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

• バブルソート、選択ソート、挿入ソートは計算量が$O(n^2)$です。

• マージソートは常に$O(n\log n)$で安定ですが、追加の記憶領域が必要です。

• クイックソートは平均$O(n\log n)$で高速ですが、最悪の場合は$O(n^2)$になります。

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

安定なソートは、同じキーのデータの元の順序を保ちます。ヒープソートは最悪でも$O(n\log n)$です。

例: 部署順の社員一覧を年齢で安定ソートすると、同じ年齢の中では部署順が保たれます。