図書館ソートのソースを表示

{{Infobox algorithm
|class=[[ソート]]
|image=
|data=[[配列]]
|time=<math>O(n^2)</math>
|best-time=<math>O(n)</math>
|average-time=<math>O(n\log n)</math>
|space=<math>O(n)</math>
|optimal=?
}}

'''図書館ソート'''（としょかんソート）またはライブラリソート（[[英語|英]]: library sort, '''gapped insertion sort'''）は、[[ソート]]の[[アルゴリズム]]の一つ。[[挿入ソート]]をベースとし、挿入操作を高速化するために配列に隙間（''gap''）を設けるもの。名前は次のアナロジーに由来する:

<blockquote>司書が長い本棚にアルファベット順に本を陳列しようとしているとする。本棚は左端がAで始まり、右端のZの終わりまで隙間なく本で埋まっている。司書が新しい本をBの区画に収めるには、Bの区画に適切な位置を見つけ、スペースを空けるために後ろのすべての本をずらす必要がある。これが[[挿入ソート]]である。しかし、各区画の間(BとCの境界など)に空白があったなら、新しい本のためにずらすべき本の数は少なくて済む。これが図書館ソートの基本的な原理である。</blockquote>

このアルゴリズムは[[2004年]]<ref>https://arxiv.org/abs/cs/0407003</ref>に[[Michael A. Bender]]、[[Martín Farach-Colton]]および[[Miguel Mosteiro]]によって提案され、[[2006年]]<ref name="definition">
{{cite journal | journal=Theory of Computing Systems | volume=39 | issue=3 | pages=391 | year=2006  | author1=Bender, M. A.|author2 =  Farach-Colton, M.|authorlink2 = Martin Farach-Colton|author3= Mosteiro M. | title=Insertion Sort is O(n log n) | doi = 10.1007/s00224-005-1237-z }}</ref>に発表された。

図書館ソートはそのベースとなる[[挿入ソート]]と同様、[[安定ソート|安定]]な[[比較ソート]]であり、[[オンラインアルゴリズム]]として実行可能。しかしながら O(n<sup>2</sup>) の挿入ソートとは異なり、高確率で[[クイックソート]]と同じクラスの O(n log n) で実行できることが示されている。この改良のために使われた仕組みは[[スキップリスト]]のものとほぼ同様である。論文では、完全な実装も、挿入や調整(''rebalance'')のような重要な部分の正確なアルゴリズムも示されていない。図書館ソートが他のソートアルゴリズムと比べて現実的にどの程度有効であるかを議論するには、さらなる情報が必要となる。

基本的な挿入ソートと比べて、図書館ソートの欠点は隙間のための空間を要することである。スペースの量や配置は実装による。論文において、必要な配列の長さは ''(1 + ε)n'' <ref name="definition" /> だとされているが、''ε'' の選び方は何も推奨されていない。

[[挿入ソート]]の弱点の一つに、[[メモリ]]への書き込みが高コストである時に、多くの回数の swap 操作が負荷になりうるというものがある。図書館ソートは要素の移動が少なくなるように改良されているので、挿入段階が多少改善される可能性があるが、調整の段階で追加のコストを要する。加えて、ランダムなデータセットからの挿入操作がキャッシュから外れたメモリにアクセスする可能性があり、特に大きなデータセットについて、[[参照の局所性]]が[[マージソート]]に劣る。

==実装==
===アルゴリズム ===
要素数 n の配列が与えられたとする。これに隙間を入れて、要素数 ''(1 + ε)n'' にする。以下、挿入と調整の操作を繰り返す (''log n'' 回)。挿入段階では、挿入済みの要素と同じ数の要素を挿入する。挿入済みの部分に[[二分探索]]を適用することで挿入位置を見つけ、そしてスペースが見つかるまで要素を swap していく。調整段階では、配列の各要素の間に隙間を挿入する。

このアルゴリズムの重要な手順は次の3つである:

1. [[二分探索]]:
挿入済みの要素からなる部分に二分探索を適用することで、次の要素の挿入位置を見つける。区間の中央がスペースだった時は、単に左か右の方へ移動すればよい。

2. 挿入:
見つかった位置に要素を挿入し、次のスペースまで後ろの各要素を1つずつずらしていく。

3. 調整:
配列の各要素の間にスペースを挿入する。これには[[線形時間]]がかかる。このアルゴリズムは ''log n'' 回の繰り返しからなるので、調整にかかる時間は全体で O(n log n) 時間だけである。

===擬似コード===

 '''proc''' rebalance(A, begin, end)
     r ← end
     w ← end * 2
     '''while''' r >= begin
         A[w+1] ← gap
         A[w] ← A[r]
         r ← r - 1
         w ← w - 2

 '''proc''' sort(A)
     n ← length(A)
     S ← new array of n gaps
     '''for''' i ← 1 to floor(log2(n) + 1)
         '''for''' j ← 2^i to 2^(i+1)
             ins ← binarysearch(S, 2^(i-1))
             insert A[j] at S[ins]

ここで <code>binarysearch(A, k)</code> は配列 {{mvar|A}} の最初の {{mvar|k}} 個の要素に[[二分探索]]を適用する。ただし隙間は無視する。挿入は要素が詰まったところより隙間を優先する。

==参考文献==
{{reflist}}

==外部リンク==
*[http://www.cs.sunysb.edu/~bender/newpub/BenderFaMo06-librarysort.pdf Gapped Insertion Sort]

{{ソート}}
{{DEFAULTSORT:としよかんそおと}}
[[Category:ソート]]