C言語プログラミング クイックソート

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;
}
}
/* クイックソート関数ここまで */

近日中にクイックソートを再帰で書いたプログラムを掲載する予定です。

Wikipedia ソート
Wikipedia クイックソート
Wikipedia C言語