どうも〜 シュモクザメです。
今日はソートの一種であるクイックソートを実装していきます。
かなり有名なソートで課題などにもよく出てくると思うので是非参考にしてください。
全体のコードは一番下に貼ってあります。
クイックソートのアルゴリズム解説
クイックソートのアルゴリズムを画像にしてみました。
まず整列したい配列の中から一つ値を取り出してそれをピボットとします。
それからその配列を添字番号の小さい順に
ピボットの値以下の値の要素だけの配列
ピボット
ピボットの値以上の値の要素だけの配列
に並び替えます。
それから
ピボットの値以下の値の要素だけの配列
ピボットの値以上の値の要素だけの配列
それぞれにクイックソートをかけます。
このように再帰的に配列にクイックソートをかけていくと、
だんだんかける配列が小さくなっていって、配列の要素が1になったらそのクイックソートの処理を終えます。
要素が1ということは言い換えれば、その部分の並び替えが完了して位置が決まったってことだしね
すべてのクイックソートの処理が終わったとき配列のソートが完了しています。
コード実装
ここからは実際にコードを組んでいきましょう。
方針として
ピボットを基準に並び替える際、配列自体を分割したり、新しく作りません。
あくまで処理する配列一つの中完結させます。
そのために並び替える際は、配列の並び替える範囲を指定してその部分だけを並び替えます。
ピボットを基準に配列を並び替える関数
とりあえずコードです。
int pivot(int x[],int l,int r){
int i, j, p, t;
i=l;//配列の左側走査用
j=r-1;//配列の右側走査用
p=x[r];//pはピボット
while(1){
while(x[i]<p){
i++;
};
while(i<j&&p<x[j]){
j--;
};
if(i>=j)
break;
t=x[i];
x[i]=x[j];
x[j]=t;
}
t=x[i];
x[i]=x[r];
x[r]=t;
return i;
}この関数では配列の処理する部分からピボットを選んでそれを基準に並び替えます。
上の関数では引数に配列とint型l,rを受け取ります。
このlとrが配列の処理する範囲の左端と右端の添字です。
そして右端、つまり添字rの部分をピボットとします。
ここからの方針としては、
配列の並びの中で、添字l側(左側)にピボット以下の値の要素、
添字r側（右側）にピボット以上の値の要素を集めていきます。
まずは左側から考えていきましょう。
lの値をiに代入します。
その後x[i]がピボットより小さいかを調べて、
もし小さければiをインクリメントしてまたx[i]がピボットより小さいか調べます。
これをピボットより大きいx[i]が現れるまで繰り返していって、現れたらそこで一旦iのインクリメントを終了します。
次は右側を同様に考えていきます。
x[r]はピボット自身なのでピボットより大きいか調べる必要がありません。
なのでr-1をjに代入します。
その後x[j]がピボットより大きいかを調べて、
もし大きければjをデクリメントしてまたx[j]がピボットより大きいか調べます。
これをピボットより小さいx[j]が現れるまで繰り返していって、現れたらそこで一旦jのデクリメントを終了します。
この時点でx[i]にはピボットより大きい値、x[j]にはピボットより小さい値になっているはずなのでその二つの値を交換します。
そしたらまたそこからiとjを右と左から走査していって…
を繰り返せば最終的にiとjが衝突します。
while(1){
while(x[i]<p){
i++;
};
while(i<j&&p<x[j]){
j--;
};
if(i>=j)
break;
t=x[i];
x[i]=x[j];
x[j]=t;
}
上のコードのこの部分が以上までです。
iとjの走査はどちらもwhile で行なっています。
jの走査のwhileに
i<j
も条件として入っているのはjの走査が進みすぎてiより左側に行くのを防ぐためです。
そのwhileを抜けた後にif文が入ります。
このif文ではiとjが同じ位置にあるときは値の交換の必要がないのでbreakで防いでいます。
逆に言えばこの処理全体を無限ループwhile(1)で囲んでいるから、そのbreakに入って処理を終わらせるように設計されてるね。
この処理が終わった時点で
x[r]~x[i]はピボット以下の値を持ち、
x[i+1]~x[r-1]はピボット以上の値を持ち、
x[r]にピボットが入っている状態になります。
なのでx[i]とx[r]を交換します。
これで完全に左側にピボット以下、右側にピボット以上の要素が集まりました。
最後にピボットの位置の添字を返り値としてこの関数は終わりです。
t=x[i];
x[i]=x[r];
x[r]=t;
return i;これが上のコードのこの部分。
まあ特に言うことはないですね。
クイックソート内でクイックソートを呼び出す
void quick(int x[],int l, int r){
int v;
if(l>=r)
return;
v=pivot(x,l,r);
quick(x,l,v-1);//左側の配列にクイックソート
quick(x,v+1,r);//右側の配列にクイックソート
}ここでは先ほど作った関数pivotで配列を整列して、返ってきたピボットの位置をint型vに代入します。
その後
x[l]~x[v-1]の範囲（ピボットの左側）
x[v+1]~v[r]の範囲（ピボットの右側）
それぞれにクイックソートをかけます。
ここから再帰的にクイックソートが実行されていくのですが、
最初に説明した通り部分配列の長さが1になった時にそのクイックソートで処理を終えるために
if文で(l>=r)のときreturnするようにしています。
実際に使ってみた
ちゃんとソートできていますね。
以上がクイックソートです。
クイックソートを使うこと前提の記事をこれから書いていくつもりなのでそちらもよかったらどうぞ。
それでは〜。
全体のコード
#include <stdio.h>
void show(int x[]){
for(int i=0; i<10; i++){
printf("%d ",x[i]);
}
printf("\nxxxxxxxxxxx\n");
}
int pivot(int x[],int l,int r){
int i, j, p, t;
i=l;//配列の左側走査用
j=r-1;//配列の右側走査用
p=x[r];//pはピボット
while(1){
while(x[i]<p){
i++;
};
while(i<j&&p<x[j]){
j--;
};
if(i>=j)
break;
t=x[i];
x[i]=x[j];
x[j]=t;
}
t=x[i];
x[i]=x[r];
x[r]=t;
return i;
}
void quick(int x[],int l, int r){
int v;
if(l>=r)
return;
v=pivot(x,l,r);
quick(x,l,v-1);
quick(x,v+1,r);
}
int main(int argc, const char * argv[]) {
int x[10]={1,5,3,4,7,9,8,6,0,2};
show(x);
quick(x,0,9);
show(x);
return 0;
}
コメント