ソートのアルゴリズム

様々なソートアルゴリズムが考案されてきましたが、用途やデータの特徴、またはプログラムで使うデータ構造などに応じて、それらを的確に選ばなくてはなりません。以下の表は、代表的なソートのアルゴリズムとそれらの効率・特徴を示しています。

アルゴリズムの名前	効率	安定性	特徴
選択ソート (Selection Sort)	O(n2)	×	単純で最も直感的だが、効率が悪い
バブルソート (Bubble Sort)	O(n2)	○	単純だが効率が悪い
挿入ソート (Insertion Sort)	O(n2)	○	ぼぼ整列されているデータに対して効率的
マージソート (Merge Sort)	O(nlonn)	○	外部の記憶領域が必要
ヒープソート (Heap Sort)	O(nlonn)	×	ヒープのデータ構造を応用する
クイックソート (Quick Sort)	O(nlonn)	×	ほぼ整列されているデータに対して効率的ではない

選択ソート、バブルソートはソートのアルゴリズムの導入に紹介されるくらいで、実践で（現場で）使うことはほんとんどありません。データの特徴や問題の仕様に合わせて適切なアルゴリズムを設計することが重要です。マージソートは安定で高速、しかも実装が比較的容易なのでおすすめです。クイックソートは、理論上最速と言われていますが、安定ではないので注意が必要です。