整列

英

alignment、array、align

関

アラインメント、整列化、配列、アレイ、配列比較、アライメント

WordNet

1. especially fine or decorative clothing (同)raiment, regalia
2. an arrangement of aerials spaced to give desired directional characteristics
3. an impressive display; "it was a bewildering array of books"; "his tools were in an orderly array on the basement wall"
4. an orderly arrangement; "an array of troops in battle order"
5. be or come into adjustment with
6. place in a line or arrange so as to be parallel or straight; "align the car with the curb"; "align the sheets of paper on the table" (同)aline, line_up, adjust
7. align oneself with a group or a way of thinking (同)array
8. bring (components or parts) into proper or desirable coordination correlation; "align the wheels of my car"; "ordinate similar parts" (同)ordinate, coordinate
9. the act of adjusting or aligning the parts of a device in relation to each other
10. the spatial property possessed by an arrangement or position of things in a straight line or in parallel lines

PrepTutorEJDIC

1. 〈軍隊など〉'を'整列させる,配置する / 《文》〈人〉‘に'衣類を着せる,(特に)〈人〉'を'盛装させる / 〈U〉整列,陳列 / (…の)整列(配置)した物(人),勢ぞろい《+『of』+『名』(複数)》 / 〈U〉衣装,(特に)美しい装い

Wikipedia preview

出典(authority):フリー百科事典『ウィキペディア（Wikipedia）』「2017/07/24 16:37:32」(JST)

wiki ja

[Wiki ja表示]

ソート (sort) は、データの集合を一定の規則に従って並べること。日本語では整列（せいれつ）と訳される。（以前はその原義から分類という訳語が充てられていたが、もう使われていない）

主にコンピュータソフトにおけるリストに表示するデータに対し、全順序関係によって一列に並べることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順（しょうじゅん、ascending order）を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順（こうじゅん、descending order）という。

対象となるデータのデータ構造や必要な出力によって、使われるアルゴリズムは異なる。

概要

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

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

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

ソートアルゴリズムの分類

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

安定ソート

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

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

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

内部ソートと外部ソート

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

名称	平均計算時間	最悪計算時間	メモリ使用量	安定性	手法	備考
バブルソート	—	O(n2)	O(1)	○	交換
シェーカーソート	—	O(n2)	O(1)	○	交換
コムソート	O(n log n)	O(n2)	O(1)	×	交換	コードサイズが小さくて済む。
ノームソート	—	O(n2)	O(1)	○	交換
センタク/選択ソート	O(n2)	O(n2)	O(1)	×	選択	安定ソートとしても実装可能
ソウニユウ/挿入ソート	O(n ＋ d)	O(n2)	O(1)	○	挿入	d は置換群の反転数で、O(n2)
シェルソート	—	O(n log2 n)	O(1)	×	挿入
2分木ソート	O(n log n)	O(n log n)	O(n)	○	挿入	平衡2分探索木を使った場合
図書館ソート	O(n log n)	O(n2)	O(n)	○	挿入
マージソート	O(n log n)	O(n log n)	O(n)	○	マージ
In-place マージソート	O(n log n)	O(n log n)	O(1)	○	マージ	実装例
ヒープソート	O(n log n)	O(n log n)	O(1)	×	選択
スムースソート	—	O(n log n)	O(1)	×	選択
クイックソート	O(n log n)	O(n2)	O(log n)	×	パーティショニング	単純な実装ではメモリ使用量が O(n) になる。 ピボット値として中央値を使えば、最悪時間が O(n log n)
イントロソート	O(n log n)	O(n log n)	O(log n)	×	混成
ペイシェンスソート	—	O(n2)	O(n)	×	挿入	O(n log n) 以内にすべての最長増加部分列を探す。
ストランドソート	O(n log n)	O(n2)	O(n)	○	選択
キクウテンチ/奇偶転置ソート	—	O(n2)	O(1)	○	交換
シェアソート	—	O(n1.5)	O(1)	×	交換

次の表は、比較ソート以外のソートアルゴリズムの一覧である。そのため、下限が O(n log n) で制限されない。k はキーの長さ、s は実装で使われるチャンクのサイズである。これらの一部は、キーが十分に長く、各要素のキーが重複しないことを前提としている。すなわち、n << 2^k を仮定している（<< は「十分小さい」）。

名称	平均計算時間	最悪計算時間	メモリ使用量	安定性	n << 2k?	備考
ハトノス/鳩の巣ソート	O(n＋2k)	O(n＋2k)	O(2k)	○	○
バケットソート	O(n＋k)	O(n2)	O(nk)	○	×	入力データは定義域に一様分布すると仮定
フンフカソエ/分布数えソート	O(n＋2k)	O(n＋2k)	O(n＋2k)	○	○
LSD 基数ソート	O(nk/s)	O(nk/s)	O(n)	○	×
MSD 基数ソート	O(nk/s)	O(n (k/s) 2s)	O((k/s) 2s)	×	×
スプレッドソート	O(nk/log (n))	O(n (k - log (n))0.5)	O(n)	×	×	n << 2k の場合の計算時間だが、それ以外の場合でもソート可能
キヤクシヤソウ/逆写像ソート	O(n) ?	N/A	O(n) ?	○	×

次の表は、あまりにも性能が悪いので通常は用いられないソートアルゴリズム、および特別なハードウェアが必要なソートアルゴリズムの一覧である。

名称	平均計算時間	最悪計算時間	メモリ使用量	安定性	大小比較	備考
ボゴソート	O(n × n!)	∞	O(1)	×	○	平均時間はクヌースのシャッフルを使った場合
ボゾソート	O(n × n!)	∞	O(1)	×	○	平均時間はボゴソートの約半分に漸近する。
ストゥージソート	O(n2.71)	O(n2.71)	O(log n)	×	○
スリープソート	値の最大値×プロセス起動単位時間（実際には誤差あり）	同左	O(n)?	×	?	条件が特殊。実用の正確性が保証されない。
ビードソート	N/A	N/A	—	N/A	×	専用ハードウェアが必要
タンシユンハンケエキ/単純パンケーキソート	O(n)	O(n)	O(log n)	×	○	反転を定数時間で行えるものと仮定
ソーティングネットワーク	O(log n)	O(log n)	O(n log n)	○	×	大きさ O(n log n) の回路が必要

比較ソートの理論限界

計算理論において、n個のデータのソートは、データの大小比較のみによって行う場合、最悪計算量が最低でも O(n log n) 必要なことが知られている。O(n) で実現しているアルゴリズムは、データに対して何らかの仮定があることに注意を要する。

最悪計算量が最低でもO(n log n) 必要である略証を示す。

ソーティングはデータの並べ替えである。 n個のデータの並べ替えは置換を用いて書け、置換はn!個ある。 スターリングの公式より、n!= O(nⁿ) 。

プログラム中の分岐はif文でしか起こらない。 1回のif文でプログラム中は2つに分岐するので、 n!個の置換をすべて実現する必要なif分岐の個数をmとすると、 2^m ≧ n!= O(nⁿ) でなければならない。 したがって、ソーティングの最悪計算量は最低でも m = O(n log n) である。

メモリ使用パターンとインデックスソート

ソート対象の配列が主記憶を使い切るような（あるいは越えるような）大きさであった場合、より低速な補助記憶装置が使われるので、アルゴリズムのメモリ使用パターンが重要となる。そのような状況では、主記憶上ですべてソートできることを前提としたアルゴリズムは効率が極端に悪化する可能性がある。このような状況では、比較演算回数はあまり重要ではなくなり、ディスクとのメモリ領域のスワップ回数が重要となる。したがって、なるべくスワップ回数を増やさないようにするために、配列全体を走査する回数や比較の局所性が比較回数よりも重要となる。

例えば、再帰型のクイックソートは主記憶上では性能が良いが、ソート対象の配列が主記憶に収まらない場合はスワップが頻繁に発生して、性能が極端に低下する。したがって、そのような場合は比較回数が多くても他のアルゴリズムを使った方がよい。

対策の一つとして、ソート対象の配列の要素が（関係データベースのような）複雑なレコードだった場合、その配列をそのままソートするのではなく、比較的小さいインデックスを生成して、インデックスの配列をソートするという方法がある。インデックスをソートすれば、元の配列のソートは一回の走査で可能であるが、インデックス経由でアクセスするだけならそれをする必要もない。インデックスは元の配列のレコードよりも小さいので、メモリに収まる可能性が高くなり、スワップ問題を削減することができる。この方式を「タグソート（tag sort）」などと呼ぶこともある。

別の技法として、2つのアルゴリズムを組み合わせて、それぞれの利点を利用する方法がある。例えば、配列をチャンクに分割して個々のチャンクが主記憶上でソートできる大きさにする。チャンク内のソートはメモリ上で効率的に動作するソートアルゴリズムを使い、その結果をマージソートでマージする。これは、元の配列を単純にマージソートでソートするよりも効率が悪いが、全体をクイックソートでソートするよりもメモリ使用量が少なくてすむ。

これらの技法を組み合わせることも可能である。あまりにも巨大なデータをソートする場合、インデックスのソートにも複数のアルゴリズムを組み合わせて仮想記憶の性質に合うよう設計する必要がある。

参考文献

• 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 コード例と解説

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

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

UpToDate Contents

全文を閲覧するには購読必要です。 To read the full text you will need to subscribe.

• 1. 外反膝の小児に対するアプローチ approach to the child with knock knees
• 2. 内反膝の小児に対するアプローチ approach to the child with bow legs
• 3. 小児における斜視の評価およびマネージメント evaluation and management of strabismus in children
• 4. 中手骨軸骨折 metacarpal shaft fractures
• 5. 中手骨骨頭骨折 metacarpal head fractures

Japanese Journal

• 例題形式で探求する集合・位相 : 基礎から一般トポロジーまで(第3回)整列集合と濃度

• 数理科学 56(2), 76-83, 2018-02
• NAID 40021433012

• 選択ソートよりも駄目なソートにかんして

• 人文研究 134, 135-139, 2017-12-22
• NAID 120006376236

• 評価構造可視化のための源点沈点整列制約付き階層割当

• 応用数理 27(4), 160-167, 2017-12
• NAID 40021438245

Related Pictures

---

★リンクテーブル★

リンク元	「配列」「配列比較」「アライメント」「整列化」「アレイ」
拡張検索	「整列群」
関連記事	「列」

「配列」

　　[★]

英

sequence、arrangement、array、constellation、arrange、sequential

関

協定、経時的、系列、結果、シークエンス、シーケンス、順序、準備、筋道、整列、取り計らう、配置、配列決定、連続、連続的、逐次、結果としての、時系列、並べる、アレイ、順次、整理

PHP関数

array_unique()

	for ( $i = 0 ; $i < 5 ; $i++ ) {
		$a['w'][$i] = $i+100;
		$a['m'][$i] = 1;
	}
	for ( $i = 5 ; $i < 15 ; $i++ ) {
		$a['w'][$i] = $i+100;
		$a['m'][$i] = 2;
	}
	for ( $i = 15 ; $i < 20 ; $i++ ) {
		$a['w'][$i] = $i+100;
		$a['m'][$i] = 3;
	}

	$a['w'][5]=100;
	$a['w'][15]=100;

var_dump($a);
	$b = array_unique($a['w']); #配列 重複キー 消去

var_dump($b);

-----
array(2) { 
	["w"]=> array(20) 
		{
			[0]=> int(100) [1]=> int(101) [2]=> int(102) [3]=> int(103) [4]=> int(104) [5]=> int(100) [6]=> int(106) [7]=> int(107) [8]=> int(108) [9]=> int(109) [10]=> int(110) [11]=> int(111) [12]=> int(112) [13]=> int(113) [14]=> int(114) [15]=> int(100) [16]=> int(116) [17]=> int(117) [18]=> int(118) [19]=> int(119) } 
	["m"]=> array(20) 
		{
			[0]=> int(1) [1]=> int(1) [2]=> int(1) [3]=> int(1) [4]=> int(1) [5]=> int(2) [6]=> int(2) [7]=> int(2) [8]=> int(2) [9]=> int(2) [10]=> int(2) [11]=> int(2) [12]=> int(2) [13]=> int(2) [14]=> int(2) [15]=> int(3) [16]=> int(3) [17]=> int(3) [18]=> int(3) [19]=> int(3) } } 

array(18) {
			[0]=> int(100) [1]=> int(101) [2]=> int(102) [3]=> int(103) [4]=> int(104) [6]=> int(106) [7]=> int(107) [8]=> int(108) [9]=> int(109) [10]=> int(110) [11]=> int(111) [12]=> int(112) [13]=> int(113) [14]=> int(114) [16]=> int(116) [17]=> int(117) [18]=> int(118) [19]=> int(119) } 

配列の要素の除去

array_pop

• 配列のインデックスから、末尾にあるインデックス１つを取り除く。指定した変数の配列が空だった場合には、null が帰される。

配列の結合

• 1. +演算子。同じキーを上書きする。
• 2. array_push(array, array)とすると、出力が array([0]->array, [1]->array)になる。
• 3. array_match(out_array, add_array)これでokだが、add_array = array();だとエラーが起こるので、適当なトラップが必要。　←　array_mergeの間違えでしょ？

配列要素の結合

• implodeを用いる

$str = implode('/',$array);

配列の要素表示

• var_dump()
• print_r();

「配列比較」

　　[★]

英

alignment、sequence comparison

関

アラインメント、整列、整列化、アライメント

「アライメント」

　　[★]

英

alignment

関

アラインメント、整列、整列化、配列比較

同

alignment

「整列化」

　　[★]

英

alignment

関

アラインメント、整列、配列比較、アライメント

「アレイ」

　　[★]

英

array

関

整列、配列

「整列群」

　　[★]

英

contig

関

コンティグ、連結断片

「列」

　　[★]

英

row、tier、train

関

作条、訓練、層、連、段