並び替え

実用日本語表現辞典

並び替え

読み方：ならびかえ

順番を入れ替えるなどして並べ直すさまなどを意味する表現。並び替えること。

（2011年10月20日更新）

ウィキペディア

ソート

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/09/25 09:50 UTC 版)

ウィキペディアの表のソートについては「Help:表の作り方#再整列可能な表」を、カテゴリのソートキーについてはHelp:カテゴリ#ソートキーをご覧ください。

この項目では、整列について説明しています。16世紀スペインの神学者については「ドミンゴ・デ・ソト」をご覧ください。

ソート (英: sort) は、データの集合を一定の規則に従って並べること^[1]。日本語では整列（せいれつ）、並べ替え（ならべかえ）、分類（ぶんるい）などと訳される^[1]。

主に配列や連結リストのような、リストデータ構造に分類されるコレクション（コンテナ）に格納されている要素データを、全順序関係によって並べ替えることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順（しょうじゅん、英: ascending order）を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順（こうじゅん、英: descending order）という。

対象となるコレクションのデータ構造や必要とされる出力、また時間的コストと空間的コストの兼ね合いによって、ソートに使われるアルゴリズムは異なる。

概要

効率的なソートは、ソート済みのデータを必要とする他のアルゴリズム（探索やマージ）の最適化にとっても重要である。また、ソートされたデータの方が人間にとっても読みやすい。形式的には、その出力は以下の2つの条件を満たさなければならない。

1. 設定された順序（昇順または降順）に対して、逆になるような順序の出力があってはならない。
2. 出力は入力の並べ替えでなければならない。

情報工学や計算機科学の黎明期から、ソートは単純な問題でありながら効率的に解くことが難しく、そのためもあって盛んに研究されてきた。例えばバブルソートについては、早くも1956年には解析が行われている^[2]。しかし、21世紀初にも新たなソートアルゴリズムが発明されている（例えば、Timsort（英語版）は2002年に、図書館ソートは2004年に発表された）。すでに考案されているソートにも様々なアルゴリズムがあり、またアルゴリズムという概念を学習するのに最適なので、情報工学や計算機科学での入門的題材として広く親しまれている。例えば、分割統治法、データ構造、乱択アルゴリズム、計算量解析、O記法、時間と空間のトレードオフ、下限などが含まれる。

グラフィカルユーザインタフェース (GUI) においてよく使われるウィジェットのひとつとしてリストビュー (list view) が挙げられるが、各レコードのフィールドを表す任意のカラムについてリスト中のアイテムを昇順／降順ソートできるようになっていることが多い。

分類

計算機科学では、ソートアルゴリズムを次のように分類する。

安定ソート

詳細は「安定ソート」を参照

同じ値に関して、ソート前の順序がソート後も維持されているソートを安定ソートという。

安定ソートでないソートであっても、ソート条件に元の順序を含めることで必ず安定ソートにすることが可能である。しかしながら、別途元の順序を記憶する領域が必要になることから、内部ソートであっても外部ソートになってしまう。（→#内部ソートと外部ソート）

内部ソートと外部ソート

ソートされるデータの格納領域を変更して処理を進めていくIn-placeのソートを内部ソートという。クイックソートのような再帰を利用するアルゴリズムは、再帰のために O(log n) の領域を必要とすることからIn-placeであるか否かは議論が分かれるところであるが、これも内部ソートに含めるのが一般的である。このことから内部ソートは、ソートされるデータの格納域以外には O(1) か O(log n) の領域しか必要としない。

逆に、ソートされるデータの格納領域以外に O(n) 以上の一時的な記憶領域が必要であるソートを外部ソートという。

メモリ使用量（およびその他の計算資源の使用量）による分類である。すべての内部ソートは、インデックスや参照、複製を作成して処理することで事実上の外部ソートにすることができる。アルゴリズムとしての本質ではないので一般的には無視されるが、高速化や柔軟な処理のために冗長な記憶領域を使用する場合がある。例えば、非安定ソートアルゴリズムで安定ソートを実現する場合など。（→#安定ソート）

比較ソート

詳細は「比較ソート」を参照

個々の項目を比較演算で大小判定することを基本とするソートを比較ソートという。

比較ソートには#比較ソートの理論限界が存在する。

計算量

入力されるリストの項目数 n に基づいた計算量による分類。典型的なソートアルゴリズムでは、最善で O(n log n) 、最悪で O(n²) である。理想は O(n) である。

比較ソートでは、一般的な（ランダムに並んだ）データの並べ替えに対しては少なくとも O(n log n) の比較回数が必要である。（→#比較ソートの理論限界）

手法

汎用手法による分類。挿入、交換、選択、マージなどがある。交換ソートにはバブルソートやシェーカーソートやコムソートなどが含まれる。選択ソートにはヒープソートなどが含まれる。

再帰

再帰が必須、不可能、どちらでも可能、という分類。実装上の都合で再帰に関わる制限がある場合に注目される。

一覧

配列に格納されたn個のデータをソートする場合について、各アルゴリズムの性能を示す。 計算時間の表記に用いている記号 O（オー）については、ランダウの記号を参照。

以下の表で、n はソートすべきデータ要素数である。平均実行時間と最悪実行時間は時間計算量を示している。このとき、ソートキーの長さは一定と仮定しており、比較や交換といった操作は定数時間で行われるとする。メモリ使用量は、入力データの格納域以外に必要となる領域を示している。これらは、いずれも比較ソートである。

名称	平均計算時間	最悪計算時間	メモリ使用量	安定性	手法	備考
バブルソート	${\displaystyle n^{2}}$	出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。記事の信頼性向上にご協力をお願いいたします。（2013年5月）

• D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching.

関連項目

• 照合
• 検索
• 選択
• データベース
• sort (UNIX)

外部リンク

• Sequential and parallel sorting algorithms - 各種アルゴリズムの説明と解析
• Ricardo Baeza-Yates' sorting algorithms on the Web
• 'Dictionary of Algorithms, Data Structures, and Problems'
• Slightly Skeptical View on Sorting Algorithms Softpanorama。古典的アルゴリズムについて論じ、クイックソートの代替となるアルゴリズムを提案。
• Sorting Revisited
• The Stony Brook Algorithm Repository コード例と解説
• William Cawley Gelling, Markus E. Nebel, Benjamin Smith and Sebastian Wild: "Multiway Powersort", (September 16, 2022)

ソートアルゴリズムの視覚化

• sort algorithm visualizer - 11種類のソートアルゴリズムについて各種初期条件でのソートの様子を視覚化
• いくつかのソートアルゴリズムを視覚化したJava applet
• Sort Animation - Javaアプレットによるバブルソート、挿入ソート、クイックソート、選択ソートのアニメーション図解
• xSortLab - 別のJavaアプレット。バブルソート、挿入ソート、クイックソート、選択ソート、マージソートをアニメーション化している。ソート対象を縦の棒で示している。
• Sorting contest - 8種類のソートアルゴリズムのアニメーションを一斉に実行でき、速度の違いを体感できる。

表 話 編 歴 ソート
理論	計算複雑性理論 ランダウの記号 全順序 リスト 安定性 ソーティングネットワーク 比較ソート（英語版） 整数ソート（英語版）
交換ソート	バブルソート シェーカーソート 奇偶転置ソート コムソート ノームソート クイックソート
選択ソート	選択ソート ヒープソート スムースソート デカルト木ソート トーナメントソート
挿入ソート	挿入ソート シェルソート ツリーソート 図書館ソート ペイシェンスソート
マージソート	マージソート 多層マージソート ストランドソート
非比較ソート	基数ソート バケットソート 計数ソート プロキシマップソート 鳩の巣ソート バーストソート ビーズソート
並行ソート	バイトニックソート バッチャー奇偶マージソート シェアソート
混成ソート	ティムソート イントロソート Jソート アンシャッフルソート（英語版）
その他	トポロジカルソート パンケーキソート スパゲティソート
非効率的/ ユーモラスソート	ボゴソート ストゥージソート スリープソート エラーソート

表 話 編 歴 アルゴリズム
ソート	比較ソート バブルソート 選択ソート 挿入ソート シェルソート クイックソート マージソート ヒープソート シェーカーソート コムソート ノームソート 図書館ソート イントロソート 奇偶転置ソート 線形時間ソート 鳩の巣ソート 基数ソート バケットソート 並行ソート ソーティングネットワーク バッチャー奇偶マージソート シェアソート 非効率的 ボゴソート ストゥージソート グラフ トポロジカルソート
探索	リスト 線形探索 二分探索 木・グラフ 幅優先探索 最良優先探索 均一コスト探索 A* 深さ優先探索 反復深化深さ優先探索 深さ制限探索 双方向探索 分枝限定法 ビームサーチ 文字列 クヌース–モリス–プラット法 ボイヤー-ムーア法 エイホ–コラシック法 ラビン-カープ法 Bitap法
最短経路問題	ダイクストラ法 ベルマン–フォード法 ワーシャル–フロイド法
最小全域木	プリム法 クラスカル法
最大フロー問題 最小カット問題	フォード・ファルカーソン法 エドモンズ・カープ法
線型計画問題	シンプレックス法 カーマーカー法
順序統計量	選択アルゴリズム クイックセレクト 中央値の中央値
計算幾何学	凸包アルゴリズム
種類	近似アルゴリズム 乱択アルゴリズム 並列アルゴリズム 分散アルゴリズム 可積分アルゴリズム
その他	分割統治法 動的計画法 貪欲法 アルゴリズム作曲法
カテゴリ

Weblio日本語例文用例辞書

「並び替え」の例文・使い方・用例・文例

• 下記に示されるように並び替えられる。
• 次のリストを並び替えるために
• あなたはこの紙を並び替えてください。