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

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

概要

非常に多数のアルゴリズムが考案されている。

現在使われているソートプログラムはそのほとんどがクイックソートをベースに作られており、その計算量は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)	外部	○

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