パーティションベースの選択アルゴリズム　～売上トップ100をO(n)で求めよう～

<font color="#bbb">※ディスクレーマー：$O(n\log{n})$で問題ない場合も、たくさんあると思います。</font>
<img src='https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/348026/8a93b050-bcb3-fb05-cd5d-8b844f8eef32.png' width=512>
<font color="#aaa">（↑計算量の一覧。画像元は[こちら](https://dev.to/madisonstankevich/big-o-notation-a-brief-overview-for-the-beginner-1o13)）</font>

# はじめに
素朴にソートすると$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番目までを返す。

大きい順に並び変える際に、「マージソート」を利用する。
<img src='https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/348026/4d1412c9-386e-5938-343c-ecf571c480e6.png' width=512>
<font color="#aaa">（↑マージソートのイメージ。画像元は[こちら](https://www.google.com/url?sa=i&url=https%3A%2F%2Fwww.101computing.net%2Fmerge-sort-algorithm%2F&psig=AOvVaw3tJdI2CMA5NLjYJU8G3lGa&ust=1646797049467000&source=images&cd=vfe&ved=0CAsQjRxqFwoTCOiZgZ_LtfYCFQAAAAAdAAAAABAD)）</font>

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

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

# 解法2：ちょっと早い解法
この解法に至るヒントは
<b>「全てソートする必要はない（大きいk個が分かればいい）」</b>
ということである

「優先度付きキュー」を利用する。
<img src='https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/348026/ba844fc7-7e77-84c3-fbee-f42cdb6d46b8.png' width=512>
<font color="#aaa">（↑優先度付きキューのイメージ。画像元は[こちら](https://www.google.com/url?sa=i&url=https%3A%2F%2Ffavtutor.com%2Fblogs%2Fpriority-queue-cpp&psig=AOvVaw1HFlo6KqEpUUetLs-xuVLg&ust=1646798074219000&source=images&cd=vfe&ved=0CAsQjRxqFwoTCMj_zIfPtfYCFQAAAAAdAAAAABAD)）</font>

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

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

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

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

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

#### 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]を返せばよい

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

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

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