ソート - 通信用語の基礎知識

ソート
読み：ソート
外語：sort

　整列すること。キーとなる項目が、上から(または下から)順番に並ぶように並べ替えること。

概要
　非常に多数のアルゴリズムが考案されている。
　現在使われているソートプログラムはそのほとんどがクイックソートをベースに作られており、その計算量はO(n log n)である。

順序
　並び替える順序は、大→小、小→大、のいずれかである。それぞれ、次のように呼ぶ。

内部・外部
　並び替える際に、外部記憶(作業領域)を必要とするか否かで二つに分けることができる。

安定性
　比較基準の値が同じになる要素があった場合、ソート前とソート後で、その位置が保存されるかどうかを「ソートの安定性」という。
　保存されるソートを安定なソート、保存されない可能性があるソートを不安定なソートという。

名称	計算量		内部/外部	安定性
名称	(最悪)	(平均)	内部/外部	安定性
単純選択ソート	O(n²)	O(n²)	内部	×
バブルソート	O(n²)	O(n²)	内部	○
シェイカーソート	O(n²)	O(n²)	内部	○
コムソート	O(n²)	O(n^1.25)～O(n²)	内部	×
単純挿入ソート	O(n²)	O(n²)	内部	○
シェルソート	O(n²)	O(n^1.25)～O(n²)	内部	×
マージソート	O(n log n)	O(n log n)	外部	○
ヒープソート	O(n log n)	O(n log n)	内部	×
クイックソート	O(n²)	O(n log n)	内部	×
バケットソート	O(n)	O(n)	外部	○
基数ソート	O(mn)	O(mn)	外部	○

　単純選択ソートの安定性は通常の実装では不安定であるが、アルゴリズムの工夫で安定なソートにすることは可能。