本記事では、配列の分割方法である「パーティション」の解説・C言語での実装を確認していきます。
アルゴリズム解説では、図を用いた解説を行うため、イメージしやすい構成となっています。
パーティションは、クイックソートを理解する上で必要となる知識なので、しっかり確認していきましょう。
- パーティションのアルゴリズムの流れ
- C言語による実装方法
アルゴリズム入門書はこの一冊で十分！
パーティションのアルゴリズム
パーティションは、アルゴリズムに基づき、配列をある規則に従うように並び替える手法です。
内容自体は全く難しくないのですが、どこを交換するのか、といったことが若干わかりづらいので、じっくり見ていきましょう。
まずは、具体的な手順の前に、ザックリと何をしたいのかを確認します。
パーティションは、「ある基準値に対して、それよりも小さな値と、大きな値を左右それぞれに分ける」ということを行います。
この例では、「６」が基準値となっています。
一般的には、右端の値を基準値に設定します。
見てわかるように、基準値である「６」よりも小さな値が「６」の左側に、大きな値が「６」の右側に移動しています。
パーティションで行う内容はこれだけです。
「完成形はこんな感じなのか～」、と頭の片隅にでも置いといてください。
後は、この処理をどのように実現するのかを見ていきます。
パーティションの処理は、言葉で説明するよりも、実際のコードと図を見てもらった方がわかりやすいので、まずは partition 関数のコードから確認します。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Aは配列、pは配列の左端の添え字、rは配列の右端の添え字 int partition(int A[], int p, int r) { for (int i = p; i < r; i++) { if (A[i] <= A[r]) { swap(A, p, i); // A[p-1]とA[i]を交換する p++; } } swap(A, r, p); // A[r]とA[p]を交換する return p; // 基準値の位置を返す } |
では、この関数に沿って図で説明していきます。
引数には、パーティションによって並び替える配列と、その配列の先頭・末尾の添え字をそれぞれ渡します。
今回は、配列Aを以下のように設定します。
この場合、関数への引数は、 p = 0 、 r = 7 となります
ここで、変数 r と p の役割を説明します。
r は、配列の基準値を指す添え字であり、今回は A[r] 、すなわち「６」が基準値になります。
p は、基準値よりも大きい部分の、先頭の値を指す添え字になっています。
別の言い方をすると、基準値よりも小さい部分と大きい部分の仕切りのような役割になります。
では、説明を進めながら確認していきましょう。
ここからは、for文のループ処理に入ります。
ループ処理では、対象の配列の先頭位置から、順番に基準値との比較を行います。
まずは、 i = 0 の位置と基準値とを比較します。
書いてある通り、 A[i] が基準値よりも小さい場合、何もせずにfor文の更新を行います。
その後、再び値の比較を行います。
次は、 i = 1 の位置と、基準値を比較します。
今度は、基準値よりも小さい値であったため、値の入れ替えが発生します。
まず、 A[p]と A[i] を交換します。
その後、 p を１つずらします。
これにより、配列の先頭から、添え字が i の位置までの範囲が並び替えられました。
ここでは、「３」と「８」が並び替えられています。
そして、変数 p は、「３」と「８」のうち、基準値である「６」よりも大きい部分の先頭に移動しています。
緑の部分は、基準値よりも小さい値の集まりです。
もう少し見ていきましょう。
for文の更新により、 i が１つずれるので、今度は「５」と「６」を比較します。
今回も、基準値よりも小さい値であったため、値の入れ替えが発生します。
まず、 A[p]と A[i] を交換します。
その後、 p を１つずらします。
これにより、配列の先頭から、添え字が i の位置までの範囲がさらに並び替えられました。
ここでは、「３」「５」「８」が並び替えられています。
そして、変数 p は、「３」「５」「８」のうち、基準値である「６」よりも大きい部分の先頭に移動しています。
つまり、「３」「５」が基準値よりも小さい部分、「８」が基準値よりも大きい部分なので、 p は「８」の位置に移動します。
for文の更新により、 i が１つずれるので、今度は「１」と「６」を比較します。
再び、基準値よりも小さい値であったため、値の入れ替えが発生します。
まず、 A[p]と A[i] を交換します。
その後、 p を１つずらします。
ここまでで、「３」「５」「１」「８」が並び替えられています。
最後にもう一度だけ、説明付きで見ていきます。
for文の更新により、 i が１つずれるので、今度は「７」と「６」を比較します。
「７」は基準値よりも大きいため、何もせずにfor文の更新を行います。
残りは機械的に行います。
ここで、forループは終了します。
ここまで行うことで、この配列は、 p の位置を境目とし、このように並びます。
最後に、 A[p] と A[r] を入れ替えることで、基準値を境にして値を並び替えることができます。
これで、基準値より小さい値が基準値の左側に、基準値より大きい値が基準値の右側に並びました。
ここまでがパーティションのアルゴリズムです。
いざ説明してみると、かなり複雑っぽくなりましたが、実際はそこまで複雑じゃないので、怪しい方はもう一度コードから見直してみてください。
パーティションの実装【C言語】
最初の方にパーテーション関数のコードは載せているので、ここでは、メイン関数込みの全体のプログラムを載せます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <stdio.h> #define N 8 // 配列の全ての要素を出力する void printArray(int A[], int n) { for (int i = 0; i < n; i++) if (i == 0) printf("%d", A[i]); else printf(" %d", A[i]); printf("\n"); } // 配列の要素を入れ替える void swap(int A[], int a, int b) { int temp; temp = A[a]; A[a] = A[b]; A[b] = temp; } int partition(int A[], int p, int r) { for (int i = p; i < r; i++) { if (A[i] <= A[r]) { swap(A, p, i); // A[p-1]とA[i]を交換する p++; } } swap(A, r, p); // A[r]とA[p]を交換する // 基準値の位置を返す return p; } int main(void) { int A[N] = {8, 3, 5, 1, 7, 4, 2, 6}; printArray(A, N); int p = partition(A, 0, N-1); // パーテーションで配列を並び替える printArray(A, N); return 0; } |
パーティションの実装コードは、
23~34行目にあります。
こちらのプログラムを実行結果は、
|
1 2 |
8 3 5 1 7 4 2 6 3 5 1 4 2 6 7 8 |
となり、前の章で見てきた並びと同様になることが確認できます。
これで、パーティションの内容はおしまいです。
パーテーションについて学習した後は、是非クイックソートのアルゴリズムも学習してみてください。
では、今回はここまでとします。
お疲れさまでした。