26.1.6.30 交換分割整列

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

• 配列aと，整列すべき範囲top，tailを与えられる．

• top >=tailであれば，やることはない．

• top < tailの場合

• 範囲をa[top]〜a[p]とa[p+1]〜a[tail]に分割．
  

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

• それぞれの部分範囲を(ふつうは自分自身を使用して)整列

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