※ディスクレーマー：$O(n\log{n})$で問題ない場合も、たくさんあると思います。

（↑計算量の一覧。画像元はこちら）

はじめに

素朴にソートすると$O(n\log{n})$な問題が、$O(n)$で求まるアルゴリズムについて解説する。
「パーティションベースの選択アルゴリズム」という。

例えば以下のような問題だ。

問題

数列からk 個の最大要素を求めよ。
（つまり、最大値~k番目に大きいものまでを求めよ）
※ただし、要素がソートされている必要はない

【例】

n=6, k=3
入力：[3,4,6,5,1,2]
出力：[4,6,5]

→上位3位までに入る数列を返す（ソートの必要なし）

解法0：素朴すぎる解法

大きい順のランキングを作ってから、k番目までを返す。
大きい順に並び変える際に、

1番大きいもの...
2番目に大きいもの...
3番目...

と探していく（「選択ソート」）
これにかかる計算量は$O(n^2)$である。これでは少し遅い。

解法1：素朴な解法

上のカイゼン。
大きい順のランキングを作ってから、k番目までを返す。

大きい順に並び変える際に、「マージソート」を利用する。

（↑マージソートのイメージ。画像元はこちら）

これにかかる計算量は$O(n\log{n})$である。

十分に思えるが、さらに早くするにはどうしたらいいか？

解法2：ちょっと早い解法

この解法に至るヒントは
「全てソートする必要はない（大きいk個が分かればいい）」
ということである

「優先度付きキュー」を利用する。

（↑優先度付きキューのイメージ。画像元はこちら）

まず、配列から適当なk個を優先度付きキューに入れる（この時点でk個をソートし、最小値が先頭になるようにする）
以下の操作を繰り返す。

元の配列の、残りの要素のうち1つを見て
- キューの最小値より小さければ何もしない
- 最小値より大きければ、キューの最小値を削除し、この要素をキューにソートして挿入

この挿入にはO(logk)かかる

操作の繰り返しは n 回程度発生するので、
全体にかかる計算量は$O(n\log{k})$である。

解法3：最適な解法

上の解法では、k個については並べ替えが発生してしまっており、$O(\log{k})$かかっている。
問題ではTOPが分かればいいのであって、TOPをランキング化する必要はない。
このランキング化をどうにか辞め、全体の計算量を$O(n)$にできないか考えたい。

そこで、「パーティションベースの選択アルゴリズム」の登場。
これは、「クイックソート」にかなり似ているアルゴリズムだ。

3-1. まず、一番左の値を基準（ピボット）として、左側に[その値未満の群]と[その値以上の群]に分かれるようにする

例えば冒頭の例では
基準:3（一番左の値）なので
[3,4,6,5,1,2]
を
[3未満の群]-[3以上の群]
に分解したい。その際に以下のような手順を踏む

3-2. 左端から見てピボット以上の値と、右端から見てピボット未満の値の場所を交換する

[3,4,6,5,1,2]
は
[3,4,6,5,1,2]
3と2、4と1が交換され
[2,1,6,5,4,3]
となる。群で言うと（2,1）-（6,5,4,3）になっているイメージだ。(3-1で述べたように左側に[その値未満の群]と[その値以上の群]に分かれるようになっている！)

3-3. この操作を再帰的に繰り返す。ただし、右からk番目までの要素が入っている群だけ繰り返せばよい

クイックソートでは
[2,1]
に対しても3-2と同じことをして
[1,2]とするのだが、このソートは必要ない。

なぜなら、冒頭の問題ではk=3であり、3番目までに大きいモノを返せばいいからだ。
右側の[6,5,4,3]の群が3個以上ある時点で、[2,1]の要素がトップ3に入ってくる可能性は
ゼロなのである。

したがって、
[6,5,4,3]についてだけ3-2と同じ操作を繰り返すと
今度は、基準：6（一番右の値）
なので、3と6が交換され
[3,5,4,6]
となる。群で言うと（2,1）-（3,5,4）-（6）になっているイメージだ。
真ん中の群について繰り返すと
[3,5,4]は[3,5,4]のままだ。この場合（3）-（5,4）に分解する。

3-4. 右から「ちょうど」k番目の要素まで分解出来たら、そこで終わり。

今回は（2,1）-（3）-（5,4）-（6）となっているので、[5,4,6]を返せばよい

まとめ

クイックソートに近いが、「パーティションベースの選択アルゴリズム」の場合「いらない場所はソートしない」と切り捨てることができるので、平均$O(n)$で計算することが可能なのだ！

参考

「選択アルゴリズム」と「中央値の中央値」
http://www.flint.jp/blog/?entry=109

中央値を線形時間で選択するアルゴリズムについて
https://techblog.nhn-techorus.com/archives/15289