日本語の資料が乏しかったので,ここにまとめます。
必要な前提知識も多く、この記事単体では完結していないです。
詳しくは、参考文献等をご参照ください。
また、書かれているコードは、以下の問題で検証済みですが、
不十分であるため、コピペされる方は自己責任でお願いいたします。
Quick Select とは
「ある配列の中で、k番目に小さい値はいくつ？」に答えるアルゴリズム。
クイックソートの要領で pivot を選択し、pivotを元に、配列を分割しながら答えを探す。
愚直に考えると、ソートしてk番目をとればいいが、その場合は、最悪計算量がソートがボトルネックになり$O(nlogn)$になる。
一方、このアルゴリズムは、平均計算量$O(n)$で解くことができる。
実装方針
pivot の選択方法には、以下の方法があるが、今回は中央値の中央値をpivotにすることにした。
- 常に左の要素を採用する
- ランダムに取得した要素を採用する
- 中央値の中央値を採用する
また、pivotに対して、配列を並べ替える戦略が以下にあるが、効率がよい前者を採用した。
- Hoare partition scheme
- Lomuto partition scheme
コード
func insertionSort(a []int, left, right int) {
for i := left; i <= right; i++ {
j := i
for (j > left) && (a[j-1] > a[j]) {
a[j-1], a[j] = a[j], a[j-1]
j--
}
}
}
func median(a []int, left, right int) int {
insertionSort(a, left, right)
return a[left+(right-left)/2]
}
func partition(a []int, left, right, pivot int) int {
i := left - 1
j := right + 1
for {
i, j = i+1, j-1
for a[i] < pivot {
i += 1
}
for a[j] > pivot {
j -= 1
}
if i < j {
a[i], a[j] = a[j], a[i]
} else {
return j
}
}
}
func selectPivot(a []int, left, right int) int {
if right-left < 5 {
return median(a, left, right)
}
for i := left; i+4 <= right; i += 5 {
insertionSort(a, i, i+4)
a[i+2], a[left+(i-left)/5] = a[left+(i-left)/5], a[i+2]
}
n := right - left + 1
return innerSelect(a, left, left+n/5-1, left+n/10-1)
}
func innerSelect(a []int, left, right, kth int) int {
if left == right {
return a[left]
}
pivot := selectPivot(a, left, right)
pivotIndex := partition(a, left, right, pivot)
if kth <= pivotIndex {
return innerSelect(a, left, pivotIndex, kth)
} else {
return innerSelect(a, pivotIndex+1, right, kth)
}
}
func QuickSelect(a []int, left, right, kth int) int {
return innerSelect(a, left, right, kth)
}
参考文献
クイックセレクトの考え方の元となるクイックソートの詳細
クイックセレクトの実装の概要
- https://en.wikipedia.org/wiki/Quickselect
- http://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad09/ad09-05.pdf
- https://en.wikipedia.org/wiki/Median_of_medians