次の図のように、配列 $A$ の partition の対象となる範囲は $p$ から $r$ まで（それぞれ含む）となります。ここで partition の基準となる $A[r]$ を $x$ とします。基準となる $x$ 以下の要素が $p$ から $i$ までの範囲（$i$ を含む）に、$x$ より大きい要素が $i$ + 1 から $j$ までの範囲（$j$ を含まない）にあるように、$A$ の要素を移動してきます。$i$ は $p$ − 1、$j$ は $p$ の位置に初期化します。
毎回の計算ステップで $j$ は必ず１つ後方に進み、$A[j]$ をどちらのグループに入れるかを順番に決めていきます。グループへの入れ方は以下の２つの場合があります。
$A[j]$ が $x$ よりも大きい場合は、要素の移動は必要なく、$j$ を１つ進めて $A[j]$ を「$x$ より大きいグループ」へ含めます。
$A[j]$ が $x$ 以下の場合は、まず $i$ を１つ進めて、 $A[j]$ と $A[i]$ を交換します。$A[j]$ は $x$ 以下のグループに移動し、$j$ が１つ進められることによって $A[i]$ にあった要素は $x$ より大きいグループに含められます。
例えば、数列 $\{3, 9, 8, 1, 5, 6, 2, 5\}$ に対して partition を行うと以下のようになります。
Reference
|
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ)AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。 |