C言語: 2007年6月アーカイブ
とても人気がないように思えながらも、実はC言語を目的としてこのblogに足を運んでくださっている方、かなり多いみたいです。
これまでにソートとして挿入ソート、シェルソート、選択ソート、バブルソート、バケットソート(ビンソート)、クイックソートを紹介してきました。
また、フィボナッチ数列や階乗の再帰呼び出しについても書きましたね。
それら過去の記事に興味がある方はC言語のカテゴリーをご覧ください。
前回の最後にて告知しましたように、今回はクイックソートの再帰呼び出しバージョンです。
詳しい説明は省きますが、区間を分割するたびに自身を呼び出す仕組みになっています。
/* クイックソート関数(再帰版)ここから */
/* data[]:データ格納配列 nlef:ソートする範囲の先頭添字 nrig:ソートする範囲の末尾添字*/
void sort(int data[],int nlef,int nrig){
int i , cen , clef , temp;
if(nlef < nrig){
/*区間の中心を基準値として取得*/
cen = (nlef + nrig) / 2;
/*区間の基準値と区間の先頭を交換*/
temp = data[nlef];
data[nlef] = data[cen];
data[cen] = temp;
clef = nlef;
for(i = nlef + 1 ; i <= nrig ; i++){
/*区間の基準値の右に基準値より小さい数値を並べる*/
if(data[i] < data[nlef]){
temp = data[i];
data[i] = data[clef];
data[clef] = temp;
}
}
/*基準値を自分より小さい数値と大きい数値の間に移動する*/
temp = data[nlef];
data[nlef] = data[clef];
data[clef] = temp;
/*基準値より小さい範囲のソート*/
sort(data , nlef , clef-1);
/*基準値より大きい範囲のソート*/
sort(data , clef+1 , nrig);
}
}
/* クイックソート関数(再帰版)ここまで */
C言語について書くの、非常に久しぶりですね。
このblogにC言語プログラム目当てで来ている方がありがたいことにけっこう多いようなので、早く書こうとは思ってはいたのですが。
C言語のソート紹介シリーズ、挿入ソート、シェルソート、選択ソート、バブルソート、バケットソート(ビンソート)ときまして、今回はクイックソートについて書かせていただきます。
過去の記事に興味がある方は右側のカテゴリより「C言語」をお選びください。
クイックソートの原理について簡単に説明いたします。
並んだデータの中から一つの基準値を選び、それより大きいグループと小さいグループに分割します。
分割したグループの中でまた基準値を選び、それより大きいグループと小さいグループに分割します。
全体が順番通りに並ぶまでこの繰り返しを続けます。
名前にクイックとついています通り、他のソートアルゴリズムに対して高速だと言われています。
ただし、「平均すれば速い」ということであり「すべての場合について他のアルゴリズムより速い」わけではありません。
小規模な場合やある程度整列が済んでいる場合等、クイックソートが不向きなこともあります。
大規模なデータをクイックソートである程度まで並び替え、それから別のソート方法を使うこともあるようです。
データが「86543271」のときの使用例は以下の通りです。
・中心を基準とする。
「865(4)3271」
・基準より小さいものを左、大きいものを右に移動する。
「132(4)6578」
・基準の左右の中心を新たな基準とする。
「1 (3) 2 」4「 6 (5) 78」
・新たな基準を元に、大小で左右に分割する。
「21 (3)」4「(5) 678」
・まだ並べ変わっていない部分「21」について、基準を設けて左右に分割する。
「1(2)」345678
・完成。
「12345678」
以下、C言語で書いたクイックソートのプログラム例です。
一例であり、また、同一の値が存在する場合を考慮しておりません。実際には基準の取り方を工夫する等して、効率の向上を計ります。
ソートを行う関数部分のみです。
/* クイックソート関数ここから */
/* data[]:データ格納配列 num:配列要素数 */
void sort(int data[],int num){
int i , p , lef[num] , rig[num] , nlef , nrig , cen , clef , temp;
p = 0;
/*左端と右端の添え字を保持*/
lef[p] = 0;
rig[p] = num - 1;
while(p >= 0){
/*現在の区間の左端と右端を取得*/
nlef = lef[p];
nrig = rig[p];
p--;
/*現在の範囲のソート完了と判断してループの先頭へ*/
if(nlef >= nrig)continue;
/*区間の中心を基準値として取得*/
cen = (nlef + nrig) / 2;
/*区間の基準値と区間の左端を交換*/
temp = data[nlef];
data[nlef] = data[cen];
data[cen] = temp;
clef = nlef;
for(i = nlef + 1 ; i <= nrig ; i++){
/*区間の基準値の右に基準値より小さい数値を並べる */
if(data[i] < data[nlef]){
clef++;
temp = data[i];
data[i] = data[clef];
data[clef] = temp;
}
}
/*基準値を自分より小さい数値と大きい数値の間に移動する*/
temp = data[nlef];
data[nlef] = data[clef];
data[clef] = temp;
/*分割した区間のそれぞれの左端と右端を保持*/
p++;
lef[p] = nlef;
rig[p] = clef-1;
p++;
lef[p] = clef+1;
rig[p] = nrig;
}
}
/* クイックソート関数ここまで */
近日中にクイックソートを再帰で書いたプログラムを掲載する予定です。