Goで Quick Select を書いた - Qiita

日本語の資料が乏しかったので,ここにまとめます。 必要な前提知識も多く、この記事単体では完結していないです。 詳しくは、参考文献等をご参照ください。 また、書かれているコードは、以下の問題で検証済みですが、 不十分であるため、コピペされる方は自己責任でお願いいたします。 Quick Select とは 「ある配列の中で、k番目に小さい値はいくつ？」に答えるアルゴリズム。 クイックソートの要領で pivot を選択し、pivotを元に、配列を分割しながら答えを探す。 愚直に考えると、ソートしてk番目をとればいいが、その場合は、最悪計算量がソートがボトルネックになり$O(nlogn)$になる。 一方、このアルゴリズムは、平均計算量$O(n)$で解くことができる。 実装方針 pivot の選択方法には、以下の方法があるが、今回は中央値の中央値をpivotにすることにした。 常に左の要素を採用する