中央値の中央値
中央値の中央値をピボット値として採用すると、ピボット値は以下の様な特性を持つ。
n 5 {\displaystyle {\frac {n}{5}}} 個の小配列に分割した時、その小配列のうち半数( n 5 × 1 2 = n 10 {\displaystyle {\frac {n}{5}}\times {\frac {1}{2}}={\frac {n}{10}}} 個)の小配列では、各小配列の中央値がピボット値(中央値の中央値)以下である。また、各小配列の中には、必ず各中央値以下である要素が3個存在する。よって、その n 10 {\displaystyle {\frac {n}{10}}} 個の各小配列には、ピボット値以下の要素が少なくとも3個以上存在するはずなので、全体としては、 3 n 10 {\displaystyle {\frac {3n}{10}}} 個の要素がピボット値以下である。 同様に、もう半数の小配列には、ピボット値以上の要素が少なくとも3個以上存在するはずなので、全体としては、 3 n 10 {\displaystyle {\frac {3n}{10}}} 個の要素がピボット値以上である。
よって、そのピボット値を使用して配列を2分割をした時、その分割点は少なくとも上位30%から70%の間に存在することになるので、次の探索対象となる配列の要素数は、必ず元の配列の要素数の一定の割合(最悪でも3割、最善だと7割)に減少させることができる。
例として、0から99までの100個の乱数列での中央値の中央値を考えると以下のようになる。
ここで、背景が
赤色:ピボット値(中央値の中央値)
灰色:ピボット値(中央値の中央値)以下の要素
白色:ピボット値(中央値の中央値)以上の要素
である。
また、(5要素ずつの)各小配列の中では昇順で並べ替えて可視化してあるので、3行目が各小配列の中央値のみを抽出した配列になっている(実際には並べ替える必要はなく、可視化の都合である。実際には各小配列の中での中央値さえ計算できればよい)。 加えて、小配列自体はその中央値同士を比較して昇順で並べ替えて可視化してあるので、最終的に、赤色のピボット値より左上にある(30個=元の配列の要素数の3割の)値は、必ずピボット値以下である。また同様に、右下にある値は必ずピボット値以上であることが分かる。