イントロソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動
イントロソート
クラス ソート
データ構造 配列
最悪計算時間
平均計算時間

イントロソート: introsort)は、David Musser英語版 が1997年に設計した、クイックソートヒープソートを組み合わせたソートアルゴリズムである。

最初はクイックソートを行い、再帰のレベルがソートされた要素数(の対数)を超えるとヒープソートに切り替える。時間計算量は最悪でも O(n log n) であり、同時に典型的なデータに対するソートではクイックソートに匹敵する性能を示す。

イントロソートは、クイックソートやヒープソートと同様、比較ソートである。

クイックソートは、性能がピボット(データ列を分割する境界値)の選択に強く依存するという欠点があった。 例えばデータ列の先頭や最後尾をピボットに選ぶと、ほぼソートされた入力について最悪の性能を示す。 ニクラウス・ヴィルトはこれを避けるため、データ列の中央の要素をピボットに選ぶようにしたが、工夫をこらした並びに対しては最悪で O(n2) となる。 よりロバストな方法として先頭、最後尾、中央の値の中央値をピボットに選ぶアルゴリズム(median-of-3 pivot)もある。大抵のデータ列のソートはこれでほとんどうまくいくが、データ列を工夫することで性能を大幅に低下させることができ、DoS攻撃に利用できる。

Musser は、median-of-3 pivot クイックソートが最悪値を示すようなデータであっても、例えば要素数 100000 のデータに対してイントロソートの実行時間がクイックソートの 1/200 になったことを報告している。

Musser は Robert Sedgewick が考案したキャッシュメモリの効果を考慮したソートアルゴリズムも検討した。それは、細かい部分について挿入ソートを1回最後に行うというものである。彼によると、イントロソートではキャッシュミス率は2倍になるが、両端キューを使った実装では劇的に性能を改善できるため、テンプレートライブラリに保持すべきだとしている(特に、キャッシュの保持されている間にソートを行わないこともあるため)。

クイックソートと同様の考えを適用した選択アルゴリズムとして、アントニー・ホーアクイックセレクトがある。 選択アルゴリズムも同様にイントロソートの考えを適用でき、イントロセレクト英語版の計算量は、最悪時間でも線形時間となる(クイックセレクトの最悪時間は O(n2))。

2000年6月、SGI C++ Standard Template Library で、Musser のイントロソートの手法を利用した不安定ソートの実装をした[1]。ヒープソートに切り替える再帰の深さは引数で指定でき、最終段は Sedgewick の挿入ソートを使う方式である。挿入ソートに切り替わる再帰の深さは16だった。

擬似コード[編集]

クイックソートの内部で呼び出す分割関数(partition)とヒープソートheapsort)は既に実装されているものとすると、イントロソートは以下のように簡潔に書ける:

from typing import Any
from collections.abc import MutableSequence
# ソート関数
# 内部で introsort を呼び出す。
#
# @param seq   - ソートする配列
# @param keyFn - 配列のキー値を計算する関数
def sort(seq: MutableSequence[Any], keyFn: Callable[[Any], int]):
    from math import log2, floor
    n = len(seq)
    maxDepth = floor(2 * log2(n))
    introsort(seq, keyFn, 0, n - 1, maxDepth)

# イントロソート
# 再帰が指定した深さに達するまでクイックソートし、
# ソートが完了するまでヒープソートする。
#
# @param seq      - ソートする配列
# @param keyFn    - 配列のキー値を計算する関数
# @param first    - ソート範囲の開始インデックス
# @param last     - ソート範囲の終端インデックス
# @param maxDepth - 再帰の最大深さ
def introsort(seq: MutableSequence[Any], keyFn: Callable[[Any], int], first:int, last:int, maxDepth: int):
    if last <= first:
        return
    elif maxDepth == 0:
        heapsort(seq, keyFn, first, last)
    else:
        pivotIndex = partition(seq, keyFn, first, last)
        introsort(seq, keyFn, first, pivotIndex - 1, maxDepth - 1)
        introsort(seq, keyFn, pivotIndex + 1, last, maxDepth - 1)

なお sort 内で最大深さ(maxDepth)として配列の長さの対数に 2 を掛けたものを選んでいるが、この係数は任意の値でよい。

脚注[編集]

[脚注の使い方]

参考文献[編集]

外部リンク[編集]