ソート

ソート (英えい: sort) は、データの集合しゅうごうを一定いっていの規則きそくに従したがって並ならべること。日本語にほんごでは整列せいれつ（せいれつ）、並ならべ替がえ（ならべかえ）、分類ぶんるい（ぶんるい）などと訳やくされる。

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

対象たいしょうとなるコレクションのデータ構造こうぞうや必要ひつようとされる出力しゅつりょく、また時間じかん的てきコストと空間くうかん的てきコストの兼かね合あいによって、ソートに使つかわれるアルゴリズムは異ことなる。

概要がいよう

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

1. 設定せっていされた順序じゅんじょ（昇順しょうじゅんまたは降順こうじゅん）に対たいして、逆ぎゃくになるような順序じゅんじょの出力しゅつりょくがあってはならない。
2. 出力しゅつりょくは入力にゅうりょくの並ならべ替がえでなければならない。

情報じょうほう工学こうがくや計算けいさん機き科学かがくの黎明れいめい期きから、ソートは単純たんじゅんな問題もんだいでありながら効率こうりつ的てきに解とくことが難むずかしく、そのためもあって盛さかんに研究けんきゅうされてきた。例たとえばバブルソートについては、早はやくも1956年ねんには解析かいせきが行おこなわれている。しかし、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 はソートすべきデータ要素ようそ数すうである。平均へいきん実行じっこう時間じかんと最悪さいあく実行じっこう時間じかんは時間じかん計算けいさん量りょうを示しめしている。このとき、ソートキーの長ながさは一定いっていと仮定かていしており、比較ひかくや交換こうかんといった操作そうさは定数ていすう時間じかんで行おこなわれるとする。メモリ使用しよう量りょうは、入力にゅうりょくデータの格納域かくのういき以外いがいに必要ひつようとなる領域りょういきを示しめしている。これらは、いずれも比較ひかくソートである。

名称めいしょう	平均へいきん計算けいさん時間じかん	最悪さいあく計算けいさん時間じかん	メモリ使用しよう量りょう	安定あんてい性せい	手法しゅほう	備考びこう
バブルソート	$n^{2}$	$n^{2}$	$1$	○	交換こうかん
シェーカーソート	$n^{2}$	$n^{2}$	$1$	○	交換こうかん
コムソート	$n\log n$	$n^{2}$	$1$	×	交換こうかん	コードサイズが小ちいさくて済すむ。
ノームソート	$n^{2}$	$n^{2}$	$1$	○	交換こうかん
センタク/選択せんたくソート	$n^{2}$	$n^{2}$	$1$	×	選択せんたく	安定あんていソートとしても実装じっそう可能かのう
ソウニユウ/挿入そうにゅうソート	$n^{2}$	$n^{2}$	$1$	○	挿入そうにゅう	最良さいりょう計算けいさん時間じかんが$\Theta (n)$になる。
シェルソート	$n\log n$	≧$n^{1.5}$	$1$	×	挿入そうにゅう	最悪さいあく$\Omega (n^{\frac {3}{2}})$や$\Omega (n^{\frac {4}{3}})$の数列すうれつが実用じつよう化かされている。
2分木ぶんぎソート	$n\log n$	$n\log n$	$n$	○	挿入そうにゅう	平衡へいこう2分ふん探索たんさく木きを使つかった場合ばあい
図書館としょかんソート	$n\log n$	$n^{2}$	$n$	○	挿入そうにゅう
マージソート	$n\log n$	$n\log n$	$n$	○	マージ	連結れんけつリストの場合ばあいは$O(1)$外部がいぶメモリ。
In-place マージソート	$n\log ^{2}n$	$n\log ^{2}n$	$1$	○	マージ	実装じっそう例れい
ヒープソート	$n\log n$	$n\log n$	$1$	×	選択せんたく
スムースソート	—	$n\log n$	$1$	×	選択せんたく
クイックソート	$n\log n$	$n^{2}$	$\log n$	×	パーティショニング	メモリはコールスタック（素朴そぼくな実装じっそうでは $\Omega (n)$ になる）
イントロソート	$n\log n$	$n\log n$	$\log n$	×	混成こんせい	メモリはコールスタック
ペイシェンスソート	—	$n^{2}$	$n$	×	挿入そうにゅう	$O(n\log n)$ 以内いないにすべての最長さいちょう増加ぞうか部ぶ分列ぶんれつを探さがす。
ストランドソート	$n\log n$	$n^{2}$	$n$	○	選択せんたく
キクウテンチ/奇偶きぐう転置てんちソート	$n^{2}$	$n^{2}$	$1$	○	交換こうかん
シェアソート	$n^{1.5}$	$n^{1.5}$	$1$	×	交換こうかん

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

名称めいしょう	平均へいきん計算けいさん時間じかん	最悪さいあく計算けいさん時間じかん	メモリ使用しよう量りょう	安定あんてい性せい	n << 2k?	備考びこう
ハトノス/鳩ばとの巣すソート	$n+2^{k}$	$n+2^{k}$	$2^{k}$	○	○
バケットソート	$n+k$	$n^{2}$	$nk$	○	×	入力にゅうりょくデータは定義ていぎ域いきに一様いちよう分布ぶんぷすると仮定かてい
フンフカソエ/分布ぶんぷ数すうえソート	$n+2^{k}$	$n+2^{k}$	$n+2^{k}$	○	○
LSD 基数きすうソート	$nk/s$	$nk/s$	$n$	○	×
MSD 基数きすうソート	$nk/s$	$n(k/s)2^{s}$	$(k/s)2^{s}$	×	×
スプレッドソート	$nk/\log n$	$n(k-\log n)^{0.5}$	$n$	×	×	n << 2k の場合ばあいの計算けいさん時間じかんだが、それ以外いがいの場合ばあいでもソート可能かのう
キヤクシヤソウ/逆ぎゃく写像しゃぞうソート	$n$ ?	N/A	$n$ ?	○	×

次つぎの表ひょうは、あまりにも性能せいのうが悪わるいので通常つうじょうは用もちいられないソートアルゴリズム、および特別とくべつなハードウェアが必要ひつようなソートアルゴリズムの一覧いちらんである。

名称めいしょう	平均へいきん計算けいさん時間じかん	最悪さいあく計算けいさん時間じかん	メモリ使用しよう量りょう	安定あんてい性せい	大小だいしょう比較ひかく	備考びこう
ボゴソート	$n\cdot n!$	∞	$1$	×	○	平均へいきん時間じかんはクヌースのシャッフルを使つかった場合ばあい
ボゾソート	$n\cdot n!$	∞	$1$	×	○	平均へいきん時間じかんはボゴソートの約やく半分はんぶんに漸近ぜんきんする。
ストゥージソート	$n^{2.71}$	$n^{2.71}$	$\log n$	×	○
スリープソート	値ねの最大さいだい値ち×プロセス起動きどう単位たんい時間じかん（実際じっさいには誤差ごさあり）	同左どうさ	$n$?	×	?	条件じょうけんが特殊とくしゅ。実用じつようの正確せいかく性せいが保証ほしょうされない。
ビードソート	N/A	N/A	—	N/A	×	専用せんようハードウェアが必要ひつよう
タンシユンハンケエキ/単純たんじゅんパンケーキソート	$n$	$n$	$\log n$	×	○	反転はんてんを定数ていすう時間じかんで行おこなえるものと仮定かてい
ソーティングネットワーク	$\log n$	$\log n$	$n\log n$	○	×	大おおきさ $O(n\log n)$ の回路かいろが必要ひつよう。
バイトニックソート	$\log ^{2}n$	$\log ^{2}n$	$n\log ^{2}n$	×	×	計算けいさん時間じかんとメモリ使用しよう量りょうはソーティングネットワークとして実装じっそうしたときの値ね
バッチャー奇偶きぐうマージソート	$\log ^{2}n$	$\log ^{2}n$	$n\log ^{2}n$	×	×	計算けいさん時間じかんとメモリ使用しよう量りょうはソーティングネットワークとして実装じっそうしたときの値ね

比較ひかくソートアルゴリズムの最悪さいあく計算けいさん量りょうの下界げかい

ソートを行おこなう際さい、要素ようそ間あいだの順序じゅんじょの決定けっていを2要素ようその大小だいしょう関係かんけいの比較ひかく処理しょりのみを用もちいて行おこなうことにする。この時とき、$n$要素ようそからなるリストをソートするアルゴリズムの最悪さいあく比較ひかく回数かいすうは$\Omega (n\log n)$回かいとなる。すなわち、どんな比較ひかくソートアルゴリズムであっても入力にゅうりょくによっては（一般いっぱん的てきな入力にゅうりょくに対たいしては）漸近ぜんきん的てきに$n\log n$回かいの比較ひかくが必要ひつようとなる。

この理由りゆうを説明せつめいする。ある比較ひかくソートアルゴリズムが与あたえられた際さい、様々さまざまな入力にゅうりょくに対たいする処理しょりの手順てじゅんを二分にぶん決定けってい木きとして表あらわすことができる。内部ないぶノードは2要素ようその比較ひかく処理しょりを表あらわし、内部ないぶノードから子こノードへの2本ほんの枝えだは比較ひかく結果けっかに応おうじた処理しょりを表あらわす。また、葉はは処理しょりの終了しゅうりょうを表あらわす。この時とき、木きの高たかさが最悪さいあく比較ひかく回数かいすうとなる。$n$要素ようそからなるリストが入力にゅうりょくされる時とき、どのような二分にぶん決定けってい木きを作つくったとしても、木きの高たかさが$\Omega (n\log n)$になることを示しめす。二分にぶん決定けってい木きの高たかさを$m$とした時とき、木きの形かたちによらず、葉はの数かずは$2^{m}$以下いかになる。$n$要素ようそからなるリストの（添字そえじの）置換ちかんは$n!$個こ存在そんざいするが、任意にんいの入力にゅうりょくに対たいしてアルゴリズムが正ただしい出力しゅつりょくをするためには、$n!$個この異ことなるリストを入力にゅうりょくした際さい、それらがすべて異ことなる葉はに到達とうたつできるようにしなければならない。よって、葉はの数かずは$n!$以上いじょうでなければならない。以上いじょうより、$n!\leq 2^{m}$である。スターリングの公式こうしきより$\left({\frac {n}{e}}\right)^{n}<n!$なので、$\left({\frac {n}{e}}\right)^{n}<2^{m}$。よって、$m>\log _{2}\left({\frac {n}{e}}\right)^{n}=n(\log _{2}n-\log _{2}e)$。よって$m=\Omega (n\log n)$。

以上いじょうより、任意にんいの比較ひかくソートアルゴリズムの最悪さいあく計算けいさん量りょうは$\Omega (n\log n)$となる。すなわち、比較ひかくソートアルゴリズムの最悪さいあく計算けいさん量りょうの下界げかいは漸近ぜんきん的てきには$n\log n$となる。

マージソート、ヒープソートなどの比較ひかくソートアルゴリズムの最悪さいあく計算けいさん量りょうは$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 コード例れいと解説かいせつ
• 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種類しゅるいのソートアルゴリズムのアニメーションを一斉いっせいに実行じっこうでき、速度そくどの違ちがいを体感たいかんできる。