26.1.6.30 交換分割整列

交換分割整列のアルゴリズムでも,再帰的メソッドを使います.その概略は以下のとおりです.

ただし前範囲の要素のどれもが,後範囲の要素のどれよりも小さくなるようにする.

ここで問題となるのが範囲の分割で,あらかじめ中央値(median)がかかわっているわけではないので,不適切な分割,たとえば1個とその残りというような分割を続けると能率が落ちる可能性があります.そのため,分割の基準値を全体の平均値としたり,先頭・中央・末尾の3値の中央値としたりする研究が盛んに行なわれています.ここではプログラムを簡単にするために,先頭の分担を分割の基準値として採用するやり方を紹介しておきます.