図書館ソート

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

図書館ソート

クラス	ソート
データ構造	配列
最悪計算時間	$O(n^{2})$
最良計算時間	$O(n)$
平均計算時間	$O(n\log n)$
最悪空間計算量	$O(n)$

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

このアルゴリズムは2004年にMichael A. Bender、Martín Farach-ColtonおよびMiguel Mosteiroによって提案され、2006年に発表された。

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

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

挿入ソートの弱点の一つに、メモリへの書き込みが高コストである時に、多くの回数の 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]

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

外部リンク

• Gapped Insertion Sort