中央値の中央値（median of medians） external_link

時間計算量 = $O(n^2)$

---

📌著者の名字の頭文字を取ってBFPRTとも呼ばれる。

これはおおよその中央値mを求めるアルゴリズムである。
おおよそとは中央値mが30〜70パーセンタイルに位置するということである。
(例えると100個のデータでは30番目〜70番目の間にある値を中央値として選択するということ。)

このアルゴリズムはクイックセレクトの基本的な考え方なので説明を記載している。
実践ではクイックセレクトを使用されたい。

アルゴリズム

• Step 1. サイズnの配列を1グループ5要素のグループに分割する。（最後のグループは5以下かもしれない。）

  📌ここでは5を使用している。この場合、求める中央値mは30％〜70％の範囲に位置するが、5を超える場合、中央値mは25％〜75％の範囲に位置することになる。

• Step 2. グループごとにソートし各グループの中央値を集めた集合をつくり、この集合に対してソートを行い中央値を求める。

  📌この集合に対し Step 1. からの操作を繰り返すという方法もある。
  この場合、中央値mは20〜80パーセンタイルに位置することになる。
  また、ときど選択に失敗する場合がある。
  例えば、データ数 $n=5^x-1$ で最後の要素が30パーセンタイルより小さい値だった場合である。
  クイックセレクトではこの方法を採用しているが選択の失敗はクイックセレクトに大きな影響を与えない。

擬似コード

非安定内部

MedianOfMedians5(ARRAY, LEFT, RIGHT)
    // the first call argument is (ARRAY, 0, ARRAY.size()-1).
    // Note:This algorithm shuffles the contents of the array.

    size = 5
    if ((RIGHT - LEFT) < size) return Median(ARRAY, LEFT, RIGHT)

    j = LEFT
    for (i=LEFT; i<=RIGHT; i+=size) {
        subRight = i + size - 1
        if (RIGHT < subRight) subRight = RIGHT

        m = Median(ARRAY, i, subRight)
        Swap(ARRAY[j], ARRAY[m])
        j++
    }
     
    return Median(ARRAY, LEFT, j-1)
}

Median(ARRAY, LEFT, RIGHT) {
    InsertionSort(ARRAY, LEFT, RIGHT)
    return floor(LEFT + (RIGHT - LEFT)/2)   // avoid overflow
}

Cコード

 external_link

時間計算量の算出

$$\begin{aligned} T(n) &= 5\text{要素グループの挿入ソート時間} \times \text{グループ数}\\ &= 5^2 \times \lceil \frac{n}{5} \rceil = 5n\\ &= O(n)\\ \\ T_2(n) &= \text{中央値の挿入ソート時間}\\ &= O(\lceil \frac{n}{5} \rceil^2)\\ &= O((\frac{1}{5})^2 n^2)\\ &= O(n^2)\\ \end{aligned}$$

🌏 Map

same layer	lower layer