ソート

読み:ソート
外語:sort 英語
品詞:さ変名詞

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

目次

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

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

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

コメントなどを投稿するフォームは、日本語対応時のみ表示されます


KisoDic通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club