クイックソート
大量のデータをソートする
これまでのソートは、大規模なデータをソートするには時間がかかります
しかし、C.A.R.Hoare が1960年に開発したクイックソートは、飛躍的に速くソートすることができます
クイックソートは、基本的に小規模のデータには不向きです
クイックソートのアルゴリズムは、一つの要素を基準とし
基準値より大きい（もしくは同じ）グループと小さいグループに分けます
さらに、このグループを同様の方法で分けていきます
このように、小さいグループと大きいグループに分け
全てのグループの要素が1つになるまでこの作業を繰り返します
最良の場合は、双方のグループの数がほぼ同じの状態でソートされる状態ですが
一方のグループの要素が1で、もう一方に残り全ての状態は最悪です
この確立は基準値の選択方法で異なり、たとえば基準値を最初のインデックスにするとした場合
ほぼ整列している状態のソートに非常に弱くなってしまうでしょう
この対策として、基準値の選択に何らかの不定な計算式を用いたりする方法が考えられます
実際に作成するソースで重要なことは、グループの範囲の保存です
常に各グループの開始インデックスと終了インデックスを保存する必要があります
この場では、グループに分けたあとに配列に値を保存しておくことにします
int * quickSort(int *ary , int last_index) {
int aryL[32] , aryR[32];
int L , R , i = 1 , j , Ladd;
aryL[1] = 0;
aryR[1] = last_index - 1;
for (L = aryL[i] , R = aryR[i] ; i ; L = aryL[i] , R = aryR[i] , i-- ) {
if (L >= R) continue;
exchangeOfValues(ary + L , ary + (L + R) / 2);
for (j = L + 1 , Ladd = L ; j <= last_index ; j++) {
if (*(ary + L) > *(ary + j)) {
Ladd++;
exchangeOfValues(ary + Ladd , ary + j);
}
}
exchangeOfValues(ary + Ladd , ary + L);
i++;
aryL[i] = L; //左側の範囲
aryR[i] = Ladd - 1;
i++;
aryL[i] = Ladd + 1; //右側の範囲
aryR[i] = R;
}
return ary;
}
void exchangeOfValues(int *x , int *y) {
int tmp;
tmp = *x; *x = *y ; *y = tmp;
return;
}
変数 L と R には、グループ分けするインデックス範囲が入り
aryLとaryRは、グループの範囲を格納しておくためのスタック配列です
LとRをループの最初で比較することで、要素を確認しています
グループ分けの必要がなければ、別のグループを配列から参照します
exchangeOfValue()関数は、値を交換する関数です
この関数を呼び出す時、交換する要素が同じ場合もありますが
等価比較で制御するよりも、無意味な交換をさせたほうが速いことが多いといわれます
C言語のように、再帰処理が可能な言語の場合は再帰を用います
再帰を用いることで、先ほどのスタック配列を使用する必要がなくなります
これは、再帰がスタック(LIFO)処理で呼び出し元に帰る性質があるからです
int * quickSort(int *ary , int first_index , int last_index) {
int j , Ladd;
if (first_index < last_index) {
exchangeOfValues(ary + first_index , ary + (first_index + last_index) / 2);
for (j = first_index + 1 , Ladd = first_index ; j <= last_index ; j++) {
if (*(ary + first_index) > *(ary + j)) {
Ladd++;
exchangeOfValues(ary + Ladd , ary + j);
}
}
exchangeOfValues(ary + Ladd , ary + first_index);
quickSort(ary , first_index , Ladd - 1);
quickSort(ary , Ladd + 1 , last_index);
}
return ary;
}
void exchangeOfValues(int *x , int *y) {
int tmp;
tmp = *x; *x = *y ; *y = tmp;
return;
}
また、少しアルゴリズムの表現が異なりますが
次のような処理にすると、可読性があり非常に見やすいでしょう
int * quickSort(int *ary , int first_index , int last_index) {
int i = first_index, j = last_index , key = *(ary + (first_index + last_index) / 2);
while(1) {
while (*(ary + i ) < key) i++;
while (*(ary + j ) > key) j--;
if (i >= j) break;
exchangeOfValues(ary + i , ary + j);
i++; j--;
}
if (first_index < i - 1) quickSort(ary , first_index , i - 1);
if (last_index > j + 1) quickSort(ary , j + 1 , last_index);
return ary;
}
void exchangeOfValues(int *x , int *y) {
int tmp;
tmp = *x; *x = *y ; *y = tmp;
printf("%d <-> %d\n" , *x , *y);
return;
}
基準値keyとそれよりも小さい値 i、大きい値 j の3つの変数しか使いません
最初のインデックスから基準値より大きい値が出るまで i をインクリメントし
最後にインデックスから基準値より小さい値が出るまで j をデクリメントします
i と j が不正な位置でなければ、exchangeOfValues()関数でそれを入れ換えます
これを i が j よりも大きい数になるまで繰り返します
通常クイックソートを使用する場合、ある程度適当なところまでクイックソートし
それ以降は挿入ソートを用いたりすることで、より効率のよいソートが実現できる
挿入ソートはある程度整列している配列をソートする場合はもっとも高速だからです