|
ソート () は、データの集合を一定の規則に従って並べること。日本語では整列（せいれつ）と訳される。（以前はその原義から分類という訳語が充てられていたが、もう使われていない〔パンチカードシステムの時代には、下位の桁から順に分類しては併合することがまさしく整列であった（O(''n'') のバケットソートになる）。〕） 主にコンピュータソフトにおけるリストに表示するデータに対し、全順序関係によって一列に並べることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順（しょうじゅん、）を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順（こうじゅん、）という。 対象となるデータのデータ構造や必要な出力によって、使われるアルゴリズムは異なる。 == 概要 == 効率的なソートは、ソート済みのデータを必要とする他のアルゴリズム（探索やマージ）の最適化にとっても重要である。また、ソートされたデータの方が人間にとっても読みやすい。形式的には、その出力は以下の2つの条件を満たさなければならない。 # 設定された順序（昇順または降順）に対して、逆になるような順序の出力があってはならない。 # 出力は入力の並べ替えでなければならない。 情報工学や計算機科学の黎明期から、ソートは単純な問題でありながら効率的に解くことが難しく、そのためもあって盛んに研究されてきた。例えばバブルソートについては、早くも1956年には解析が行われている〔Bubble Sort: An Archaeological Algorithmic Analysis Owen Astrachan〕。多くの人は既に解決済みの問題と考えているが、現在も新たなソートアルゴリズムが発明されている（例えば、図書館ソートが最初に発表されたのは2004年である）。様々なアルゴリズムがあり、アルゴリズムという概念を学習するのに最適なので、情報工学や計算機科学での入門的題材として広く親しまれている。例えば、分割統治法、データ構造、乱択アルゴリズム、計算量解析、O記法、時間と空間のトレードオフ、下限などが含まれる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ソート」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Sorting algorithm 」があります。 スポンサード リンク
|