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

目次 概要 特徴 順序 内部・外部 安定性 主なソート

概要

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

現在使われているソートプログラムはそのほとんどがクイックソートをベースに作られており、その計算量はO(n log n)である。

特徴

順序

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

• 大→小 ‐ 降順
• 小→大 ‐ 昇順

内部・外部

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

• 内部ソート ‐ 外部記憶が必要ない
• 外部ソート ‐ 外部記憶が必要である

安定性

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

保存されるソートを安定なソート、保存されない可能性があるソートを不安定なソートという。

主なソート

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

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

リンク

関連する用語
なめる
ソートの安定性
内部ソート
外部ソート
グレーディングソート
イントロソート
計算量
オー記法

[再検索] [戻る]