イントロソートのソースを表示

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

'''イントロソート'''（{{lang-en-short|introsort}}）は、{{仮リンク|David Musser|en|David Musser}} が1997年に設計した、[[クイックソート]]と[[ヒープソート]]を組み合わせたソート[[アルゴリズム]]である。

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

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

== 背景 ==
クイックソートは、性能がピボット（データ列を分割する境界値）の選択に強く依存するという欠点があった。
例えばデータ列の先頭や最後尾をピボットに選ぶと、ほぼソートされた入力について最悪の性能を示す。
[[ニクラウス・ヴィルト]]はこれを避けるため、データ列の中央の要素をピボットに選ぶようにしたが、工夫をこらした並びに対しては最悪で {{math|O(''n''<sup>2</sup>)}} となる。

このようなクイックソートの性能の悪化を起こりにくくする方法としては、先頭、最後尾、中央の値の中央値をピボットに選ぶアルゴリズム（{{en|median-of-3 pivot}}）がある。大抵のデータ列のソートはこれでほとんどうまくいくが、データ列を工夫することで性能を大幅に低下させることができ、[[DoS攻撃]]に利用できるという弱点がある。すなわち、ユーザの入力データに対して整列処理を行う場合、悪意ある入力によって意図的に負荷を強める攻撃が可能になるという脆弱性を抱えることになる。

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

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

2000年6月、[[シリコングラフィックス|SGI]] C++ [[Standard Template Library]] で、Musser のイントロソートの手法を利用した不安定ソートの実装をした<ref>[http://www.sgi.com/tech/stl/stl_algo.h stl_algo.h]</ref>。ヒープソートに切り替える再帰の深さは引数で指定でき、最終段は Sedgewick の挿入ソートを使う方式である。挿入ソートに切り替わる再帰の深さは16だった。

== 擬似コード ==
[[クイックソート]]の内部で呼び出す分割関数（{{mono|partition}}）と[[ヒープソート]]（{{mono|heapsort}}）は既に実装されているものとすると、イントロソートは以下のように簡潔に書ける：
<syntaxhighlight lang="python">
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)
</syntaxhighlight>

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

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
* {{cite journal | last=Musser | first=David | title=Introspective Sorting and Selection Algorithms | url= http://www.cs.rpi.edu/~musser/gp/introsort.ps | doi=10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-# | journal=Software: Practice and Experience | volume=27 | issue=8 | publisher=Wiley | year=1997 | pages=983–993}}
* Niklaus Wirth. "Algorithms and Data Structures". Prentice-Hall, Inc., 1985. ISBN 0-13-022005-1.

== 関連項目 ==
* {{仮リンク|イントロセレクト|en|introselect}}
: クイックソートと同様の発想に基づく[[選択アルゴリズム]]である[[クイックセレクト]]に対して、イントロソートと同様のアプローチを適用した手法。最悪計算時間は {{math|O(''n''<sup>2</sup>)}} から線形時間に改善される。

== 外部リンク ==
* [http://ralphunden.net/content/tutorials/a-guide-to-introsort/ "A guide to Introsort"] by Ralph Unden. Javaによる実装例がある。

{{ソート}}
{{DEFAULTSORT:いんとろそと}}
[[Category:ソート]]