【独学するコンピュータサイエンス-アルゴリズム編-】パーティションソート
こんにちは
今回はパーティションソートについて書きます
任意の数列の最後の要素よりも大きな値と小さな値に分類するアルゴリズムのことをパーティションソートといいます
たとえば数列｛7,6,9,8,4,1,5,3｝があったとすると、この場合は最後の要素は３です。なので、3よりも大きな値と小さな値に分類します
この場合、上図のように｛1,3,9,8,4,7,5,6｝と3を分水嶺としてそれよりもおおきな値か小さな値かでデータを分けることができます。特定のIDよりも大きなものと小さなものを検索する場合に使えそうですよね。
上記はコードにすると、こんなかんじでかけます。(C++でかきました)
#include
// マクロ定義
#define MAX 100000
int A[MAX];
int p, r;
// プロトタイプ宣言(仮引数定義には、データ型を付与することを忘れずに)
int partition(int * A, int p, int r);
int main(){
// 変数定義部
int n,ret;
// 標準入力
scanf("%d",&n);
for(int i = 0; i < n; i++)
{
scanf("%d",&A[i]);
}
// パーティション関数
ret = partition(A, 0, n-1);
// 標準出力部分
for(int i = 0; i < n; i++)
{
if(i!=0) printf(" ");
if(i==ret) printf("[");
printf("%d", A[i]);
if(i==ret) printf("]");
}
printf("\n");
return 0;
}
// パーティション関数の定義
int partition(int * A, int p, int r){
int x,i,buf;
x = A[r];
i = p-1;
for(int j = p; j < r; j++)
{
if (A[j] <= x) {
i++;
buf = A[i];
A[i] = A[j];
A[j] = buf;
}
}
buf = A[i+1];
A[i+1] = A[r];
A[r] = buf;
return i+1;//パーティションの値を返す
}
くわしいコードの解説はまたあとでやります。
ソートアルゴリズムはたくさんあるので、すこしづつ理解して身に着けていくしかありません。コードを暗記してもどうせわすれるし、あまり意味がないので、そのアルゴリズムがどんなふうに動いていくのかを理解することが大切です。アルゴリズムが動くのはコンピュータのなかですが、アルゴリズムをつくるのは人間であって、それを考えるには「紙とペン」が重要だったりします。forループが絡んで、iなどのカウントパラメータが増えると、コードはとてもシンプルにみえるのですが、処理動作を頭のなかで追いかけるにはパラメータの数の2乗くらい認識するのがむずかしくなる印象をもっておくとよいかもしれません。なので、冒頭のようにコードを書くまでに紙とペンでプログラムの挙動を追いかけてみると、実装はかなり楽になります。
アルゴリズムの理解は実装力にかかわるのでエンジニアの基礎体力みたいなものですからね。
ではでは！