クイックセレクトのソースを表示

{{Infobox Algorithm|name=クイックセレクト|class=[[選択アルゴリズム]]|image=[[File:Selecting quickselect frames.gif|Animated visualization of the quickselect algorithm. Selecting the 22nd smallest value.]]|caption=クイックセレクトの可視化。22番目に小さい要素を選択する|data=[[配列]]|best-time=<math>\Omega</math>(''n'')|average-time=<math>\Theta</math>(''n'')|time=О(''n''<sup>2</sup>)|space=|optimal=Yes}}

'''クイックセレクト'''（{{lang-en-short|quickselect}}）は配列内の ''k'' 番目に小さい要素を見つけるための[[選択アルゴリズム]]。[[クイックソート]]によく似たアルゴリズムで、クイックソートと同じく[[アントニー・ホーア]]に発見されたため、 '''ホーアの選択アルゴリズム'''とも呼ばれる。 <ref>{{Cite journal|last=Hoare|first=C. A. R.|year=1961|title=Algorithm 65: Find|journal=[[Communications of the ACM|Comm. ACM]]|volume=4|issue=7|pages=321–322|DOI=10.1145/366622.366647}}</ref>クイックソートと同様に、平均的なパフォーマンスは良好だが、最悪の場合のパフォーマンスは悪くなる。クイックセレクトとその派生アルゴリズムは、効率的な実装として最もよく使われる選択アルゴリズムである。

クイックセレクトは、クイックソートと同じように1つの要素をピボットとして選択し、ピボットに基づいてデータをピボットよりも小さいかに大きいか二分割するのを繰り返す。ただし、クイックソートのように分割した両方の区間に対して再帰するのではなく、クイックセレクトは一方の側、つまり検索している要素のある側にのみ再帰する。これにより、平均計算量が軽減される。平均計算量はクイックソートが <math>\Theta(n\log n)</math> なのに対してクイックセレクトは <math>\Theta(n)</math> 。最悪計算量はクイックソートと同じく <math>O(n^2)</math> 。

クイックソートと同様に、クイックセレクトは通常、[[In-placeアルゴリズム]]として実装され、 {{Mvar|k}} 番目の要素を選択するだけでなく、データを部分的にソートする。[[ソート]]との関係の詳細については、[[選択アルゴリズム]]を参照。

== アルゴリズム ==
クイックソートでは、[[線形時間]]で配列（インデックスの <code>left</code> から <code>right</code> への範囲）を特定の要素（ピボット）より小さい要素の部分配列と等しいかより大きい要素の部分配列へ分割し（partition）、部分配列にも繰り返し分割処理を行うことで目的の配列を整列させる。例えば要素 <code>list[pivotIndex]</code> をピボットとしてパーティションを実行する擬似コードは次のとおり：
 '''function''' partition(list, left, right, pivotIndex) '''is'''
     pivotValue := list[pivotIndex]
     swap list[pivotIndex] and list[right]  ''// ピボットを末尾に動かす''
     storeIndex := left
     '''for''' i '''from''' left '''to''' right − 1 '''do'''
         '''if''' list[i] < pivotValue '''then'''
             swap list[storeIndex] and list[i]
             increment storeIndex
     swap list[right] and list[storeIndex]  ''// ピボットを終了時の位置に動かす''
     '''return''' storeIndex
これは[[:en:Quicksort#Lomuto_partition_scheme|ロムトの分割法]]として知られている。ロムトの方法は、[[:en:Quicksort#Hoare_partition_scheme|ホーアの分割法]]よりも要素の交換（swap）を行う回数が多くなるため、一般にはホーアの方法がより高速であると考えられている。しかし、[[投機的実行]]を考慮すると実際にはロムトの方法がホーアの方法より速くなる場合がある。
また、ホーアの方法は双方向イテレータを要求するが、ロムトの方法は前方イテレータのみを要求するという違いがある（例えば[[連結リスト#片方向リスト|片方向リスト]]のソート）。<ref>
{{cite web
|last=Alexandrescu
|first=Andrei
|year=2020
|date=2020-05-14
|title=Lomuto's comeback
|website=dlang.org
|url=https://dlang.org/blog/2020/05/14/lomutos-comeback/
|accessdate=2022-03-23
|ref=harv
}}</ref>

クイックソートでは、分割後の両方の範囲を[[再帰]]処理するため最良の時間計算量は <math>\Omega(n\log n)</math> である。しかし選択アルゴリズムでは、目的の要素がピボットより後ろにあるか前にあるかは事前に分かるため、ソートと異なり片方の範囲のみを再帰呼び出しをすることで、最終的に目的の要素を正しい位置に置くことができる。これがクイックセレクトである。
 ''// リストの left 以上 right 以下の位置にあることが分かっている k 番目の要素を返す(left <= k <= right).''
 '''function''' select(list, left, right, k) '''is'''
     '''if''' left = right '''then'''   ''// 残りの要素が一つなら''
         '''return''' list[left]  ''// その要素を返す''
     pivotIndex  := ...     ''// left と right の間から pivotIndex を決める''
                            ''// 例えば、'' left + floor(rand() % (right − left + 1))
     pivotIndex  := partition(list, left, right, pivotIndex)
     ''// ピボットは、パーティション終了時の位置に移動してる''
     '''if''' k = pivotIndex '''then'''
         '''return''' list[k]
     '''else if''' k < pivotIndex '''then'''
         '''return''' select(list, left, pivotIndex − 1, k)
     '''else'''
         '''return''' select(list, pivotIndex + 1, right, k) 
----
クイックセレクトは[[線形時間]]で終わることが期待される優れたパフォーマンスのアルゴリズムである。クイックセレクトは[[In-placeアルゴリズム|インプレースアルゴリズム]]でもあり、[[末尾再帰|末尾呼び出し]]最適化がかかる場合や、以下のようにループで[[末尾再帰]]を排除した実装を行う場合は、定数のメモリ空間で実行できる。
 '''function''' select(list, left, right, k) '''is'''
     '''loop'''
         '''if''' left = right '''then'''
             '''return''' list[left]
         pivotIndex := ...     ''// select pivotIndex between left and right''
         pivotIndex := partition(list, left, right, pivotIndex)
         '''if''' k = pivotIndex '''then'''
             '''return''' list[k]
         '''else if''' k < pivotIndex '''then'''
             right := pivotIndex − 1
         '''else'''
             left := pivotIndex + 1

== 時間計算量 ==
クイックソートと同様に、クイックセレクトは平均パフォーマンスは良好だが、これは選択されたピボットに左右される。適切なピボットが選択された場合、つまり、検索する区間が一定の割合で一貫して減少する場合、検索セットのサイズは指数関数的に減少し、{{仮リンク|等比数列の和|en|Geometric_series|label=等比数列の和}}の公式から考えると、各ステップが線形であり、全体としても線形時間となる。ただし、毎回1つの要素だけ減少するなど、不適切なピボットが一貫して選択されている場合、最悪の場合のパフォーマンスの2次関数 <math>O(n^2)</math> となる。 これは、たとえば、区間の最大要素をピボットとして使用するようなクイックセレクトをソート済みの配列に使用した場合に発生する。ランダムにピボットを選ぶ場合、最悪のケースが発生する確率は指数関数的に減少するため時間計算量は[[ほとんど (数学)|ほとんど確実]]に <math>O(n)</math> になる。

== 派生 ==
ほとんど確実に線形時間で処理をする簡単な解決策は、ランダムにピボットを選択することである。

[[決定的アルゴリズム|決定的な手法]]としては、クイックソートのように3要素（例えば、先頭・中央・末尾）の[[中央値]]をピボットに選ぶ戦略が有効である。これにより、現実でよくある部分的にソートされたデータに対して線形のパフォーマンスが得られる。ただし、不自然な並びでは依然として最悪計算量になる可能性がある。 {{仮リンク|David Musser|en|David Musser|label=David Musser}}は、その戦略に対する攻撃を可能にする「3要素の中央値キラー」シーケンスについて説明している。彼はこれを動機として{{仮リンク|イントロセレクト|en|introselect|label=イントロセレクト}}を開発した。

より洗練されたピボット戦略を使用することで、最悪の場合でも線形パフォーマンスを保証できる。これを実現できるのが[[中央値の中央値]]だが、ピボットの計算のオーバーヘッドは高いため、実際にはあまり使用されない。始めはクイックセレクトを使って、ある程度の回数で終了しなかった場合に中央値の中央値を使うことで、高速の平均ケースパフォーマンスと線形の最悪ケースパフォーマンスの両方を達成できる。この手法を使うのが{{仮リンク|イントロセレクト|en|introselect|label=イントロセレクト}}である。

平均時間計算量についてより細かく計算すると、少なくとも <math>n(2+2\log 2+o(1)) \leq 3.4n + o(n)</math> 以下である（これは中央値の場合で、他の''k''の方が高速）。 <ref>[https://11011110.github.io/blog/2007/10/09/blum-style-analysis-of.html Blum-style analysis of Quickselect], [[David Eppstein]], October 9, 2007.</ref>{{仮リンク|フロイド・リベストのアルゴリズム|en|Floyd%E2%80%93Rivest_algorithm|label=フロイド・リベストのアルゴリズム}}ではより複雑なピボット戦略によって 3/2 の改善を果たしている。この場合、 <math>1.5 n + \Theta(n^{1/2})</math> となる（これは中央値の場合で、他の''k''の方が高速）。

== 関連項目 ==

* {{仮リンク|フロイド・リベストのアルゴリズム|en|Floyd–Rivest algorithm|label=フロイド・リベストのアルゴリズム}}
* {{仮リンク|イントロセレクト|en|Introselect|label=イントロセレクト}}
* [[中央値の中央値]]

== 出典 ==
{{Reflist}}

== 外部リンク ==

* " [https://www.mathworks.com/matlabcentral/fileexchange/68947-qselect qselect] "、 ''Matlab、ManolisLourakisのクイックセレクトアルゴリズム''

{{アルゴリズム}}

{{DEFAULTSORT:くいっくせれくと}}
[[Category:アルゴリズム]]