選択アルゴリズム

コンピュータサイエンス において、選択アルゴリズムとは、数値などの順序付け可能な値のコレクションから 番目の最小値を見つけるアルゴリズムです。このアルゴリズムで見つけられる値は番目の順序統計量と呼ばれます。選択には、特殊なケースとして、コレクション内の最小値、中央値、最大値の要素を見つける問題が含まれます。選択アルゴリズムには、クイック選択や中央値の中央値アルゴリズムなどがあります。これらのアルゴリズムを値のコレクションに適用すると、ビッグオー記法を使用して表現すると線形時間がかかります。すでに構造化されているデータの場合は、より高速なアルゴリズムが可能な場合があります。極端な例として、すでにソートされた配列での選択には時間がかかります。 ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle O(n)}$ ${\displaystyle O(1)}$

問題の説明

選択問題のアルゴリズムは、値のコレクションと数値を入力として受け取ります。これらの値の ${\displaystyle k}$うち番目に小さい値を出力しますが、問題のバージョンによっては、最小の値のコレクションを出力します。これが明確に定義されるためには、値を最小から最大の順序でソートできなければなりません。たとえば、値は整数、浮動小数点数、または数値キーを持つ他の種類のオブジェクトである可能性があります。ただし、それらが既にソートされているとは想定されていません。多くの場合、選択アルゴリズムは、比較ソート アルゴリズムのように、比較ベースの計算モデルに制限されます。比較ソートアルゴリズムでは、アルゴリズムは任意の 2 つの値の相対的な順序を決定できる比較演算にアクセスできますが、これらの値に対して他の種類の算術演算を実行することはできません。^{[ 1 ]} ${\displaystyle k}$ ${\displaystyle k}$

問題を単純化するために、この問題に関するいくつかの研究では、値がすべて互いに異なると仮定している[ ^{2 ]か}、互いに同じ値を持つアイテムのペアに順序を割り当てるために何らかの一貫したタイブレーク方法が使用されていると仮定しています。問題の定義におけるもう1つのバリエーションは、順序付けられた値の番号付けに関するものです。最小値は、配列のゼロベースの番号付けのようにを設定することによって取得されるのでしょうか、それとも、最小値、2番目に小さい値などに対する通常の英語の慣例に従って ${\displaystyle k=0}$を設定することによって取得されるのでしょうか。この記事では、Cormen らが使用した慣例に従います。それによれば、すべての値は異なり、最小値は から取得されます。^{[ 2 ]} ${\displaystyle k=1}$ ${\displaystyle k=1}$

これらの規則を用いると、値の集合の中で最大値はと設定することで得られる。が奇数の場合、集合の中央値は と設定することで得られる。が偶数の場合、中央値には2つの選択肢があり、それぞれ を切り捨てるか切り上げるかによって得られる。すなわち、の場合は下限中央値、の場合は上限中央値となる。^{[ 2 ]} ${\displaystyle n}$ ${\displaystyle k=n}$ ${\displaystyle n}$ ${\displaystyle k=(n+1)/2}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k=n/2}$ ${\displaystyle k=n/2+1}$

アルゴリズム

ソートとヒープ選択

ベースライン アルゴリズムとして、値のコレクション内で 番目の最小値の選択は、次の 2 つの手順で実行できます。 ${\displaystyle k}$

• コレクションを並べ替える
• ソート アルゴリズムの出力が配列の場合は、その番目の要素を取得します。それ以外の場合は、ソートされたシーケンスをスキャンして番目の要素を見つけます。 ${\displaystyle k}$ ${\displaystyle k}$

この手法にかかる時間は、主にソートステップで、比較ソートを使用する時間を必要とします。^{[ 2 ] [ 3 ]}整数ソートアルゴリズムが使用される場合もありますが、これらは通常、特殊な選択アルゴリズムを使用した場合の線形時間よりも遅くなります。しかし、この手法の単純さは魅力的であり、特に、高度に最適化されたソートルーチンがランタイムライブラリの一部として提供されている一方で、選択アルゴリズムが提供されていない場合に有効です。中程度のサイズの入力の場合、実行時間における定数要素が小さいため、ソートは非ランダム選択アルゴリズムよりも高速になる可能性があります。^{[ 4 ]}この手法では、コレクションのソート済みバージョンも生成されます。これは、後の計算、特に の他の選択肢を持つ選択に役立ちます。^{[ 3 ]} ${\displaystyle \Theta (n\log n)}$ ${\displaystyle k}$

選択ソートなどの、一度に 1 つの項目を生成するソートアルゴリズムの場合、スキャンはソートと並行して実行することができ、番目の要素が見つかったらソートを終了できます。最終的な優勝者に敗退したチームが 2 位を決めるために別のミニトーナメントを行う、シングルエリミネーショントーナメントの敗者復活戦ブラケットの 1 つの設計は、この手法の例として考えることができます。^{[ 5 ]}この最適化をヒープソートに適用すると、時間で番目の最小値を選択できるヒープ選択アルゴリズムが生成されます。^{[ 6 ]}これは、が に比べて小さい場合は高速ですが、の値が大きくなると、中央値の検索に使用される 選択のように、に低下します。 ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle O(n+k\log n)}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle O(n\log n)}$ ${\displaystyle k}$ ${\displaystyle k=n/2}$

ピボット

多くの選択方法は、入力から特別な「ピボット」要素を選択し、この要素との比較によって残りの入力値を2つのサブセット（ピボットより小さい要素の集合と、ピボットより大きい要素の集合）に分割することに基づいています。アルゴリズムは、 とこれらの集合のサイズの比較に基づいて、番目の最小値がどこにあるかを決定します。特に、の場合、番目の最小値はにあり、同じ選択アルゴリズムを に適用することで再帰的に見つけることができます。の場合、番目の最小値がピボットであり、すぐに返すことができます。残りのケースでは、番目の最小値はにあり、より具体的にはの位置にある要素です。内のこの位置にある値を探す選択アルゴリズムを再帰的に適用することで見つけることができます。^{[ 7 ]} ${\displaystyle n-1}$ ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k\leq |L|}$ ${\displaystyle k}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle k=|L|+1}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle R}$ ${\displaystyle k-|L|-1}$ ${\displaystyle R}$ ${\displaystyle R}$

関連するピボットベースのクイックソートアルゴリズムと同様に、入力を と に分割することは、これらのセットの新しいコレクションを作成することによって、または指定されたリストまたは配列データ型をその場で分割する方法によって行うことができます。詳細は、入力コレクションの表現方法によって異なります。^{[ 8 ]}ピボットを他のすべての値と比較する時間は です。^{[ 7 ]}ただし、ピボット手法はピボットの選択方法が異なり、それが各再帰呼び出しにおける部分問題の大きさに影響します。これらの方法の効率はピボットの選択に大きく依存します。ピボットの選択が適切でない場合、この方法の実行時間は まで遅くなる可能性があります。^{[ 4 ]} ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle O(n)}$ ${\displaystyle O(n^{2})}$

• もしピボットが入力のちょうど中央値にあるとしたら、各再帰呼び出しは最大で前回の呼び出しの半分の値しか持たず、合計回数は等比級数で となる。しかし、 ${\displaystyle O(n)}$中央値を求めること自体が、元の入力全体に対する選択問題である。選択アルゴリズムへの再帰呼び出しによって中央値を求めようとすると、呼び出しごとに問題のサイズが減少することはないため、無限再帰に陥る。^{[ 7 ]}
• クイックセレクトは、入力値からピボットを一様にランダムに選択します。これは、プルーンと検索アルゴリズムとして記述できます。^{[ 9 ]}クイックソートの変種で、同じピボット戦略を持ちますが、クイックソートが2つの部分コレクションとをソートするために2回の再帰呼び出しを行うのに対し、クイックセレクトはこれら2回の呼び出しのうち1回のみを行います。その期待時間は^{[ 2} ]です。^{[ 7 ] [ 9 ]}任意の定数[に対して、その比較回数が[超過する確率は[10 ^]において超指数的に小さいです。^{[ 10 ]} ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle O(n)}$ ${\displaystyle C}$ ${\displaystyle Cn}$ ${\displaystyle C}$
• クイックセレクトのバリエーションであるフロイド–リベストアルゴリズムは、あるサンプルサイズのデータ値のサブセットをランダムにサンプリングし、次にサンプルの位置のやや上と下の 2 つの要素を再帰的に選択してピボットを選択する。この選択により、が 2 つのピボットの間に挟まれる可能性が高くなり、そのためピボット後には、再帰呼び出しのためにピボット間の少数のデータ値のみが残される。この手法では、期待される比較回数である を実現できる。^{[ 11 ]}フロイドとリベストは、元の研究で、再帰サンプリング方式によって の項を まで小さくできると主張したが、その分析の正確さは疑問視されてきた。^{[ 12 ] [ 13 ]}代わりに、より厳密な分析により、彼らのアルゴリズムのバージョンでは、この項に対して が達成されることが示された。^{[ 14 ]}クイックセレクトとフロイド・リベストアルゴリズムの通常の解析では、真の乱数生成器の使用を前提としていますが、対数的に多くの真のランダムビットのみをシードした疑似乱数生成器を使用するフロイド・リベストアルゴリズムのバージョンは、高い確率で線形時間で実行できることが証明されています。^{[ 15 ]} ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle rk/n}$ ${\displaystyle k}$ ${\displaystyle n+\min(k,n-k)+o(n)}$ ${\displaystyle o(n)}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n\log n}})}$

中央値の中央値法におけるピボット選択の視覚化。図では、5つの要素の各セットが点の列として示され、上から下へ昇順に並べられています。これらの中央値（中央の列の緑と紫の点）を左から右へ昇順に並べ、中央値の中央値をピボットとして選択した場合、左上象限の要素はピボットより小さくなり、右下象限の要素はピボットより大きくなります。これは、ピボットによって多くの要素が除去されることを示しています。 ${\displaystyle 3n/10}$ ${\displaystyle 3n/10}$

• 中央値の中央値法では、入力を 5 つの要素から成るセットに分割し、他の非再帰的方法を使用して、各セットの中央値をセットごとに定数時間で求めます。次に、このメソッドは自分自身を再帰的に呼び出して、これらの中央値の中央値を求めます。得られた中央値の中央値をピボットとして使用して、 の分割を生成します。したがって、個の要素に関する問題は、個の要素 (ピボットを求めるため) と最大で個の要素 (ピボット使用後) に関する 2 つの再帰問題に削減されます。これら 2 つの再帰サブ問題の合計サイズは最大で であるため、合計時間を に加算する等比級数として解析できます。クイック選択とは異なり、このアルゴリズムはランダムではなく決定論的です。[ ^{2 ] [ 4 ] [ 5 ]これ}は、線形時間の決定論的選択アルゴリズム^として知られており、^{[ 5 [ 2 ] [ 4 ] [ 9 ] [ 16 ]}しかし、時間制限における高い定数係数により、実際にはクイック選択よりも遅くなり、^{[ 3 ] [ 9 ]}中程度のサイズの入力の場合はソートよりも遅くなります。^{[ 4 ]} ${\displaystyle n/5}$ ${\displaystyle \max(|L|,|R|)\leq 7n/10}$ ${\displaystyle n}$ ${\displaystyle n/5}$ ${\displaystyle 7n/10}$ ${\displaystyle 9n/10}$ ${\displaystyle O(n)}$ ${\displaystyle O(n)}$
• イントロセレクトなどのハイブリッドアルゴリズムは、最悪ケースの時間を保証する中央値の中央値へのフォールバックを伴うクイックセレクトの実用的なパフォーマンスを達成するために使用できます。^{[ 17 ]} ${\displaystyle O(n)}$

工場

またはから遠い の値に対する、既知の比較回数が最も少ない決定論的選択アルゴリズムは、1976 年にArnold Schönhage、Mike Paterson、Nick Pippengerによって導入されたファクトリーの概念に基づいています。^{[ 18 ]}これらは、比較を使用して小さな部分順序を組み合わせることにより、入力値の小さなサブセットに対して特定のタイプの部分順序を構築する方法です。非常に単純な例として、あるタイプのファクトリーは、1 要素の部分順序のシーケンスを入力として受け取り、これらの順序の要素のペアを比較して、2 要素の全順序セットのシーケンスを出力として生成します。このファクトリーへの入力として使用される要素は、まだ何とも比較されていない入力値、または他のファクトリーによって生成された「無駄な」値のいずれかになります。ファクトリーベースのアルゴリズムの目的は、異なるファクトリーを組み合わせ、いくつかのファクトリーの出力を他のファクトリーの入力に入力することで、最終的に、ある要素（番目に小さい要素）が他のいくつかの要素よりも大きく、他のいくつかの要素よりも小さいという半順序を得ることです。これらのファクトリーを注意深く設計することで、中央値探索に適用した場合に最大で 回の比較を行うアルゴリズムが得られます。の他の値の場合、比較の回数はより少なくなります。^{[ 19 ]} ${\displaystyle k}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k-1}$ ${\displaystyle n-k}$ ${\displaystyle 2.942n}$ ${\displaystyle k}$

並列アルゴリズム

選択のための並列アルゴリズムは、1975年にレスリー・ヴァリアントがアルゴリズムを解析するための並列比較ツリーモデルを導入して以来研究されてきました。このモデルでは、線形数の比較を使用した選択には、最小値や最大値を選択する場合でも並列ステップが必要であることが証明されました。^{[ 20 ]}その後、研究者らは、この制限に一致するステップで選択を行う並列^{アルゴリズムを発見しました。 [ 21 ] [ 22 ]}ランダム化並列比較ツリーモデルでは、制限されたステップ数と線形数の比較で選択を実行できます。 ^{[ 23 ]}より現実的な並列RAMコンピューティングモデルでは、排他的読み取りと排他的書き込みのメモリアクセスにより、プロセッサと時間的に同時に選択を実行でき、時間とプロセッサ数の両方で最適です。^{[ 24 ]}同時メモリアクセスにより、一般にわずかに高速な並列時間が可能になり、^{[ 25 ]}時間制限の項はに置き換えることができます。^{[ 26 ]} ${\displaystyle \Omega (\log \log n)}$ ${\displaystyle O(\log \log n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(n/\log n)}$ ${\displaystyle \log n}$ ${\displaystyle \log k}$

部分線形データ構造

データがすでにデータ構造に整理されている場合、値の数に対して線形以下の時間で選択を実行できる可能性があります。この簡単な例として、データがすでに配列にソートされている場合、番目の要素の選択は単一の配列検索で定数時間で実行できます。^{[ 27 ]}行と列がソートされたサイズの2次元配列に整理された値の場合、選択は の時間で実行できますが、が配列の次元に比べて小さい場合はそれよりも速くなります。 ^{[ 27 ] [ 28 ]} 1次元のソートされた配列のコレクションで、項目数が番目の配列で選択された項目より少ない場合、時間は です。^{[ 28 ]} ${\displaystyle k}$ ${\displaystyle m\times n}$ ${\displaystyle O{\bigl (}m\log(2n/m){\bigr )}}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle k_{i}}$ ${\displaystyle i}$ ${\textstyle O{\bigl (}m+\sum _{i=1}^{m}\log(k_{i}+1){\bigr )}}$

バイナリヒープ内のデータからの選択には時間 ${\displaystyle O(k)}$がかかります。これはヒープのサイズに依存せず、最良優先探索から得られる時間制限よりも高速です。^{[ 28 ] [ 29 ]}この同じ手法は、より一般的には、ヒープ順序木（各ノードが1つの値を格納する木で、ルート以外の各ノードの親の値が子の値よりも小さい）として構成されたデータに適用できます。ヒープ内で選択を実行するこの手法は、重み付きグラフでk最短経路を見つけるなど、組み合わせ最適化問題に対する複数の解をリストする問題に適用されています。これは、暗黙的に定義されたヒープ順序木の形で解の状態空間を定義し、この選択アルゴリズムをこの木に適用することによって行われます。^{[ 30 ]}逆に、線形時間選択アルゴリズムは、ヒープに関連する優先キューデータ構造のサブルーチンとして使用され、 からまでの番目の項目の抽出時間を改善しています。ここでは、反復対数です。^{[ 31 ]} ${\displaystyle n}$ ${\displaystyle O(k\log n)}$ ${\displaystyle k}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log ^{*}n+\log k)}$ ${\displaystyle \log ^{*}n}$

動的な挿入と削除が行われるデータ値のコレクションの場合、順序統計量ツリーは、ツリーノードごとに一定量の追加情報を持つ自己バランス型バイナリ検索ツリー構造を拡張し、現在のセットの番目の要素を求める挿入、削除、および選択クエリをすべて、操作ごとに で実行できるようにします。^{[ 2 ]}比較モデルの計算を超えて、バイナリ算術演算が可能な小さな整数値の場合は、操作ごとにより高速な時間が可能です。^{[ 32 ]}と の両方でメモリが線形以下であるストリーミングアルゴリズムでは、動的データの選択クエリを正確に解決することはできませんが、 count-min スケッチを使用すると、サイズが の対数因数内にあるスケッチに対して、要素の順序付けにおける位置（要素に追加された場合）がのステップ以内になる値を見つけることで、選択クエリを近似的に解決できます。^{[ 33 ]} ${\displaystyle k}$ ${\displaystyle O(\log n)}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle \varepsilon n}$ ${\displaystyle k}$ ${\displaystyle 1/\varepsilon }$

下限

上述の選択アルゴリズムの実行時間は、入力を任意の順序で処理できる選択アルゴリズムが、すべての入力を調べるのにそれだけの時間がかかるため、必要となる。入力値のいずれかが比較されない場合、その値が本来選択されるべき値である可能性があり、アルゴリズムは誤った答えを生成する可能性がある。^{[ 28 ]}この単純な議論を超えて、ランダム化と決定論的の両方の場合において、選択に必要な比較の正確な回数については、かなりの研究が行われてきた。 ${\displaystyle O(n)}$

最小値を選択するには比較が必要となる。なぜなら、選択されない値はそれぞれ、何らかの比較において最大値となることで非最小値であると判断されている必要があり、これらの値のうち2つが同一の比較において最大値となることはあり得ないからである。同じ議論は最大値の選択にも対称的に当てはまる。^{[ 14 ]} ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n-1}$

次に単純な場合は、2 番目に小さい値を選択する場合です。何度か誤った試みがなされた後、この場合の最初の厳密な下限値が 1964 年にソ連の数学者セルゲイ・キスリツィンによって発表されました。これは、2 番目に小さい値を選択するには、最小値をその他の値と区別する必要があることを観察し、この問題のアルゴリズムが行う最小値を含む比較の数を考慮することで示せます。最小値と比較された各項目は、2 番目に小さい値の候補であり、これらの値が 2 番目に小さい値として除外されるためには、2 回目の比較で別の値よりも大きいことが確認される必要があります。少なくとも 1 つの比較で値が大きく、少なくとも 2 つの比較で値が大きい場合、合計で少なくとも 回の比較が行われます。各比較の結果が、与えられた項目の数値ではなく (少なくとも 1 つの可能な順序付けとの整合性を条件として) 最大化するように選択されるという敵対的な議論は、を少なくとも に強制することが可能であること示しています。したがって、2番目に小さい値を選択するために必要な比較回数は最悪の場合で であり、これは、最小値に敗れた値の間でシングルエリミネーショントーナメントとランオフトーナメントを開催した場合に得られる回数と同じである。しかし、ランダム選択アルゴリズムの期待比較回数はこの上限よりも改善される可能性がある。例えば、6つの要素のうち2番目に小さい値を選択するには、最悪の場合で7回の比較が必要となるが、ランダム化アルゴリズムでは期待比較回数が6.5回となる可能性がある。^{[ 14 ]} ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p-1}$ ${\displaystyle n-1}$ ${\displaystyle p-1}$ ${\displaystyle n+p-2}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \log _{2}n}$ ${\displaystyle n+\lceil \log _{2}n\rceil -2}$

より一般的には、番目の要素を選択するには、平均的には少なくとも 回の比較が必要であり、これはフロイド・リベストアルゴリズムの項までの比較回数に一致する。この議論は、入力値のすべての可能な順列にわたって平均化された比較回数を持つ決定論的アルゴリズムに対して直接的に行われる。^{[ 1 ]}ヤオの原理により、これは最悪ケースの入力に対するランダム化アルゴリズムの期待される比較回数にも当てはまる。^{[ 34 ]} ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n+\min(k,n-k)-O(1)}$ ${\displaystyle o(n)}$

決定論的アルゴリズムでは、番目の要素を選択するには比較が必要であることが示されている。ここで、 はバイナリエントロピー関数である。 ^{[ 35 ]}中央値探索の特殊なケースでは、比較回数の下限がわずかに大きくなり、少なくとも の場合、となる。^{[ 36 ]} ${\displaystyle k}$ ${\displaystyle {\bigl (}1+H(k/n){\bigr )}n+\Omega ({\sqrt {n}})}$ $${\displaystyle H(x)=x\log _{2}{\frac {1}{x}}+(1-x)\log _{2}{\frac {1}{1-x}}}$$ ${\displaystyle (2+\varepsilon )n}$ ${\displaystyle \varepsilon \approx 2^{-80}}$

比較の正確な数

6つの比較を用いて5つの値の中央値を求めます。各ステップでは、次に行う比較が黄色の線分で示され、これまでに求められた順序関係（小さい＝低い、大きい＝高い）のハッセ図が青色の線分で示されています。赤色の要素は既に他の3つの要素より大きいことが分かっているため、中央値にはなりません。最終的な比較における2つの要素のうち大きい方が中央値となります。

クヌースは、最適な選択アルゴリズムに必要な正確な比較回数が分かっている とのペアをまとめた、次のような数の三角形を提示している。三角形の番目の行（最上行の から始まる）は、 個の値の入力に対する比較回数を示し、各行の番目の数は、そのサイズの入力から 番目に小さい値を選択するために必要な比較回数を示す。これらの行が対称なのは、 番目に小さい値を選択するには、最悪の場合でも番目に大きい値を選択するのと全く同じ回数の比較が必要になるためである。 ^{[ 14 ]} ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n=1}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

0

1 1

2 3 2

3 4 4 3

4 6 6 6 4

5 7 8 8 7 5

6 8 10 10 10 8 6

7 9 11 12 12 11 9 7

8 11 12 14 14 14 12 11 8

9 12 14 15 16 16 15 14 12 9

各行の左半分のエントリのほとんどは、式を使用して見つけることができます。これは、ヒープ選択に関連するアブドッラー・ハディアンとミルトン・ソーベルの方法で行われた比較の数を表しています。この方法では、シングルエリミネーショントーナメントを使用して最小値を見つけ、その後、トーナメントの勝者によって排除された値の間でさらに小さなトーナメントを繰り返し使用して、番目の最小値に達するまで次の連続する値を見つけます。^{[ 14 ] [ 37 ]}大きなエントリのいくつかは、コンピューター検索を使用して最適であることが証明されました。^{[ 14 ] [ 38 ]} $${\displaystyle n-k+(k-1){\bigl \lceil }\log _{2}(n+2-k){\bigr \rceil }.}$$ ${\displaystyle k}$

言語サポート

一般的な選択を組み込んだサポートを持つ言語はごくわずかですが、リストの最小要素または最大要素を見つける機能は多くあります。注目すべき例外として、C++とRustの標準ライブラリがあります。C ++の標準テンプレートライブラリは、期待される線形時間を保証するテンプレートメソッドを提供しています。 ^{[ 3 ]} Rustの標準ライブラリは、このデータ型のメンバー関数の複数のバリアントを提供しています。これらのバリアントはすべて、すべての入力に対して線形実行時間が保証されています。^{[ 39 ]}nth_elementselect_nth_unstableslice

Pythonの標準ライブラリには、コレクションから最小または最大の要素をソート順に返す関数heapq.nsmallestが含まれています。実装では、要素の保持に制限があり、コレクションの最初の要素に初期化されたバイナリヒープが維持されます。その後、コレクションの後続の各項目は、ヒープ内の最大または最小の要素よりも小さいか大きい場合、その要素を置き換えることができます。このアルゴリズムのメモリ使用量はheapselectよりも優れています（前者は一度にメモリ内に要素を保持するだけですが、後者はデータセット全体をメモリに操作する必要があります）。実行時間はデータの順序に依存します。最良のケースは、既にソート済みのデータの場合です。最悪のケースは、逆ソートされたデータの場合です。平均的なケースでは、ヒープの更新は少なく、ほとんどの入力要素は1回の比較だけで処理されます。例えば、10,000,000個のランダム入力から最大または最小の100個の値を抽出すると、平均で10,009,401回の比較が行われます。^{[ 40 ]}heapq.nlargest ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle O((n-k)+k\log k)}$ ${\displaystyle O(n\log k)}$

2017年以降、Matlabにはベクトル内の最大値（最小値）とそのインデックスを返す関数maxk()と関数が追加されました。Matlabのドキュメントでは、これらの関数が使用するアルゴリズムや実行時間は明記されていません。^{[ 41 ]}mink() ${\displaystyle k}$

歴史

クイックセレクトは1965年にトニー・ホーア によって分析なしで発表され、 ^{[ 42 ]} 、ドナルド・クヌースによって1971年の技術レポートで初めて分析されました。^{[ 11 ]}最初の線形時間決定論的選択アルゴリズムとして知られているのは、1973年にマヌエル・ブラム、ロバート・W・フロイド、ヴォーン・プラット、ロン・リベスト、ロバート・タージャンによって発表された中央値の中央値法です。^{[ 5 ]}彼らは、選択問題の定式化を、1883年に通常のシングルエリミネーション方式のスポーツトーナメントの設計では、2番目に優れたプレーヤーが2位を獲得することを保証しないと指摘したチャールズ・L・ドジソン（通称ルイス・キャロル）の研究に遡らせています。 ^{[ 5 ] [ 43 ]}また、1930年頃のヒューゴ・シュタインハウスの研究にも遡らせています。シュタインハウスはこの同じ考え方を引き継ぎ、最小限の数のゲーム（つまり比較）でこの保証を実現できるトーナメント設計を求めました。^{[ 5 ]}

参照

• 幾何中央値 § 計算、中央値の高次元一般化アルゴリズム
• メジアンフィルタ、画像処理におけるメジアン検出アルゴリズムの応用

参考文献

1. Cunto, Walter; Munro , J. Ian (1989). 「平均事例選択」 . Journal of the ACM . 36 (2): 270– 279. doi : 10.1145/62044.62047 . MR  1072421. S2CID 10947879  .
2. コーメン, トーマス・H. ;レイソン, チャールズ・E. ;リベスト, ロナルド・L. ;スタイン, クリフォード(2009) [1990]. 「第9章 中央値と順序統計量」.アルゴリズム入門（第3版）. MIT Press and McGraw-Hill. pp.  213– 227. ISBN 0-262-03384-4。; 「第14.1節 動的順序統計量」、339～345ページ
3. スティーヴン・S・スキエナ(2020). 「17.3: 中央値と選択」.アルゴリズム設計マニュアル. コンピュータサイエンステキスト（第3版）. シュプリンガー. pp.  514– 516. doi : 10.1007/978-3-030-54256-6 . ISBN 978-3-030-54255-9. MR  4241430 . S2CID  22382667 .
4. Erickson, Jeff (2019年6月). 「1.8: 線形時間選択」.アルゴリズム. pp.  35– 39.
5. Blum, Manuel ; Floyd, Robert W. ; Pratt, Vaughan ; Rivest, Ronald L. ; Tarjan, Robert E. (1973). 「選択のための時間境界」(PDF) . Journal of Computer and System Sciences . 7 (4): 448– 461. doi : 10.1016/S0022-0000(73)80033-9 . MR 0329916 . 
6. Brodal, Gerth Stølting (2013). 「優先キューに関する概説」. Brodnik, Andrej, López-Ortiz, Alejandro, Raman, Venkatesh, Viola, Alfredo (編).空間効率の高いデータ構造、ストリーム、アルゴリズム ― J. Ian Munro 66歳の誕生日を記念した論文集. Lecture Notes in Computer Science. Vol. 8066. Springer. pp.  150– 163. doi : 10.1007/978-3-642-40273-9_11 . ISBN 978-3-642-40272-2。
7. クラインバーグ, ジョン;タルドス, エヴァ(2006). 「13.5 ランダム分割統治法：中央値探索とクイックソート」.アルゴリズム設計. アディソン・ウェズリー. pp.  727– 734. ISBN 9780321295354。
8. たとえば、Cormen らはインプレース配列分割を使用していますが、Kleinberg と Tardos は入力をセットとして記述し、それを 2 つの新しいセットに分割する方法を使用しています。
9. Goodrich, Michael T. ; Tamassia, Roberto (2015). 「9.2: 選択」.アルゴリズム設計と応用. Wiley. pp.  270– 275. ISBN 978-1-118-33591-8。
10. Devroye, Luc (1984). 「選択アルゴリズムの実行時間の指数的限界」(PDF) . Journal of Computer and System Sciences . 29 (1): 1– 7. doi : 10.1016/0022-0000(84)90009-6 . MR 0761047 . ドゥブロイ、リュック（2001）「『見つける』確率的最悪ケース時間について（PDF） . Algorithmica . 31（3）：291–303 . doi：10.1007/ s00453-001-0046-2 . MR  1855252. S2CID  674040 .
11. フロイド, ロバート・W. ;リベスト, ロナルド・L. (1975年3月). 「選択における期待時間境界」 . Communications of the ACM . 18 (3): 165– 172. doi : 10.1145/360680.360691 . S2CID 3064709 . また、「アルゴリズム489：最小の要素を見つけるためのアルゴリズムSELECT 」（p.173、doi：10.1145/360680.360694）も参照してください。 ${\displaystyle i}$ ${\displaystyle n}$
12. Brown, Theodore (1976年9月). 「アルゴリズム489に関するコメント」. ACM Transactions on Mathematical Software . 2 (3): 301– 304. doi : 10.1145/355694.355704 . S2CID 13985011 . 
13. Postmus, JT; Rinnooy Kan, AHG ; Timmer, GT (1983). 「効率的な動的選択法」. Communications of the ACM . 26 (11): 878– 881. doi : 10.1145/182.358440 . MR 0784120. S2CID 3211474 .  
14. Knuth, Donald E. (1998). 「セクション5.3.3: 最小値比較選択」. 『コンピュータプログラミングの技法』第3巻：ソートと検索（第2版）. Addison-Wesley. pp.  207– 219. ISBN 0-201-89685-0。
15. Karloff, Howard J.; Raghavan, Prabhakar (1993). 「ランダム化アルゴリズムと疑似乱数」 . Journal of the ACM . 40 ( 3): 454– 476. doi : 10.1145/174130.174132 . MR 1370358. S2CID 17956460 .  
16. Gurwitz, Chaya (1992). 「中央値探索アルゴリズムの指導について」. IEEE Transactions on Education . 35 (3): 230– 232. Bibcode : 1992ITEdu..35..230G . doi : 10.1109/13.144650 .
17. Musser, David R. (1997年8月). 「イントロスペクティブソートおよび選択アルゴリズム」.ソフトウェア：実践と経験. 27 (8). Wiley: 983–993 . doi : 10.1002/(sici)1097-024x(199708)27:8<983::aid-spe117>3.0.co;2-# .
18. Schönhage, A. ; Paterson, M. ; Pippenger, N. (1976). 「中央値の探索」. Journal of Computer and System Sciences . 13 (2): 184– 199. doi : 10.1016 / S0022-0000(76)80029-3 . MR 0428794. S2CID 29867292 .  
19. Dor, Dorit ; Zwick, Uri (1999). 「中央値の選択」. SIAM Journal on Computing . 28 (5): 1722– 1758. doi : 10.1137/S0097539795288611 . MR 1694164. S2CID 2633282 .  
20. Valiant, Leslie G. (1975). 「比較問題における並列処理」. SIAM Journal on Computing . 4 (3): 348– 355. doi : 10.1137/0204030 . MR 0378467 . 
21. アジュタイ、ミクロス;コムロス, ヤーノス島;シュタイガー、ウェストミンスター州。シェメレディ、エンドレ(1989)。 「最適な並列選択は複雑です」。コンピュータおよびシステム科学のジャーナル。38 (1): 125–133。土井: 10.1016/0022-0000(89)90035-4。MR 0990052。 ${\displaystyle O(\log \log n)}$ 
22. アザール, ヨッシ;ピッペンガー, ニコラス(1990). 「並列選択」.離散応用数学. 27 ( 1–2 ): 49–58 . doi : 10.1016/0166-218X(90)90128-Y . MR 1055590 . 
23. Reischuk, Rüdiger (1985). 「ソートと選択のための確率的並列アルゴリズム」. SIAM Journal on Computing . 14 (2): 396– 409. doi : 10.1137/0214030 . MR 0784745 . 
24. Han, Yijie (2007). 「最適並列選択」. ACM Transactions on Algorithms . 3 (4): A38:1–A38:11. doi : 10.1145/1290672.1290675 . MR 2364962 . S2CID 9645870 .  
25. Chaudhuri, Shiva; Hagerup, Torben; Raman, Rajeev (1993). 「近似的および正確な決定論的並列選択」. Borzyszkowski, Andrzej M.; Sokolowski, Stefan (編). Mathematical Foundations of Computer Science 1993, 18th International Symposium, MFCS'93, Gdansk, Poland, August 30 – September 3, 1993, Proceedings . Lecture Notes in Computer Science. Vol. 711. Springer. pp.  352– 361. doi : 10.1007/3-540-57182-5_27 . hdl : 11858/00-001M-0000-0014-B748-C . ISBN 978-3-540-57182-7。
26. Dietz, Paul F.; Raman, Rajeev (1999). 「並列における小ランク選択とヒープ構築への応用」. Journal of Algorithms . 30 (1): 33– 51. doi : 10.1006/jagm.1998.0971 . MR 1661179 . 
27. Frederickson, Greg N.; Johnson, Donald B. (1984). 「一般化選択とランキング：ソート済み行列」. SIAM Journal on Computing . 13 (1): 14– 30. doi : 10.1137/0213002 . MR 0731024 . 
28. Kaplan, Haim; Kozma, László; Zamir, Or; Zwick, Uri (2019). 「ヒープからの選択、行ソート行列、ソフトヒープの使用」。Fineman, Jeremy T.; Mitzenmacher, Michael (編). 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8–9, 2019, San Diego, CA, USA . OASIcs. Vol. 69. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 5:1–5:21. arXiv : 1802.07041 . doi : 10.4230/OASIcs.SOSA.2019.5 . ${\displaystyle X+Y}$
29. Frederickson, Greg N. (1993). 「最小ヒープにおける選択のための最適アルゴリズム」 . Information and Computation . 104 (2): 197– 214. doi : 10.1006/inco.1993.1030 . MR 1221889 . 
30. Eppstein, David (1999). 「最短経路の探索」. SIAM Journal on Computing . 28 (2): 652– 673. doi : 10.1137/S0097539795290477 . MR 1634364 . ${\displaystyle k}$ 
31. Babenko, Maxim; Kolesnichenko, Ignat; Smirnov, Ivan (2019). 「カスケードヒープ：時間最適抽出に向けて」.計算システム理論. 63 (4): 637– 646. doi : 10.1007/s00224-018-9866-1 . MR 3942251. S2CID 253740380 .  
32. Pătraşcu, Mihai ; Thorup, Mikkel (2014). 「最適ランク、選択、および先行探索を備えた動的整数集合」.第55回IEEEコンピュータサイエンス基礎シンポジウム, FOCS 2014, フィラデルフィア, ペンシルベニア州, 米国, 2014年10月18日～21日. IEEEコンピュータソサエティ. pp.  166– 175. arXiv : 1408.3045 . doi : 10.1109/FOCS.2014.26 . ISBN 978-1-4799-6517-5。
33. Cormode, Graham; Muthukrishnan, S. (2005). 「改良されたデータストリームサマリー：count-minスケッチとその応用」. Journal of Algorithms . 55 (1): 58– 75. doi : 10.1016/j.jalgor.2003.12.001 . MR 2132028 . 
34. Chan, Timothy M. (2010). 「選択のための比較ベースの時空間下限値」. ACM Transactions on Algorithms . 6 (2): A26:1–A26:16. doi : 10.1145/1721837.1721842 . MR 2675693 . S2CID 11742607 .  
35. Bent, Samuel W.; John, John W. (1985). 「中央値を見つけるには比較が必要」. Sedgewick, Robert (編). Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6–8, 1985, Providence, Rhode Island, USA . Association for Computing Machinery. pp.  213– 216. doi : 10.1145/22145.22169 . ISBN ${\displaystyle 2n}$ 0-89791-151-2。
36. Dor, Dorit ; Zwick, Uri (2001). 「中央値選択には比較が必要」. SIAM Journal on Discrete Mathematics . 14 (3): 312– 325. doi : 10.1137/S0895480199353895 . MR 1857348 . ${\displaystyle (2+\varepsilon )N}$ 
37. Hadian, Abdollah; Sobel, Milton (1969年5月).バイナリエラーレス比較を用いた-番目に大きい値の選択（レポート）. ミネソタ大学統計学部技術報告書. 第121巻. hdl : 11299/199105 . ${\displaystyle t}$
38. Gasarch, William ; Kelly, Wayne ; Pugh, William (1996年7月). 「小さいサイズの の 番目に大きいサイズを見つける」ACM SIGACT News . 27 (2): 88– 96. doi : 10.1145/235767.235772 . S2CID 3133332 . ${\displaystyle i}$ ${\displaystyle n}$ ${\displaystyle i,n}$ 
39. 「プリミティブ型スライス」 . Rust標準ライブラリ. 2025年10月12日閲覧。
40. 「heapqパッケージのソースコード」 . Pythonライブラリ. 2023年8月6日閲覧。;ベストケースデータでのアルゴリズムパフォーマンスの比較へのリンクも参照してください。
41. "mink: 配列のk個の最小要素を見つける" . Matlab R2023aドキュメント. Mathworks . 2023年3月30日閲覧。
42. Hoare, CAR (1961年7月). 「アルゴリズム65: Find」. Communications of the ACM . 4 (7): 321– 322. doi : 10.1145/366622.366647 .
43. ドジソン、チャールズ・L. (1883). 『ローンテニストーナメント：賞金の真の決定方法と現在の方法の誤りの証明』ロンドン: マクミラン社.ウィルソン、ロビン、モクテフィ、アミルーシュ編（2019年）「ローンテニストーナメント」『チャールズ・L・ドジソンの数学的世界』（ルイス・キャロル著）オックスフォード大学出版局、129ページ、ISBNも参照。 9780192549013。

「 https://en.wikipedia.org/w/index.php?title=Selection_algorithm&oldid=1331691857」より取得