クイックソート（Qiuck Sort）は1962年、C.A.R.Hoareが考案したソートアルゴリズムです。
構造は単純で、内部整列の中では最高速の部類に入るのではないかと思います。
クイックソート（Qiuck Sort）は、安定したソートアルゴリズムではありません。
この点は気をつける必要があります。
ある適当な値を選び出し、その値を中心に大小に分けていくという方法で、中心になる値のことを、枢軸（Pivot）と呼びます。
以下の例で枢軸はleftの値にしてみました。
またこの例では再帰を使用しているのでスタックを多く使用します。この点は注意が必要です。
- データの個数が、１個なら終了。
- 枢軸をleftの位置にし、交換する値の場所を ｊ とする。
- 枢軸を元に値を大小に分割交換していく。
- 枢軸を適切な位置に入れる。
- 枢軸より右側と、左側を同じ関数で分割交換する。(再帰)
*ptrはint型変数の配列への先頭ポインタ、leftはデータの先頭、rightはデータの最後を示す値です。
void quick_sort(int *ptr, int left, int right)
{
int i, j;
if(left >= right)
return;
j = left;
for(i=left+1; i <= right; i++)
if(*(ptr+i) < *(ptr+left))
swap(ptr+(++j), ptr+i);
swap(ptr+left, ptr+j);
quick_sort(ptr, left, j-1);
quick_sort(ptr, j+1, right);
}
void swap(int *ptr1, int *ptr2)
{
int w;
w = *ptr1;
*ptr1 = *ptr2;
*ptr2 = w;
}
また
if(*(ptr+i) < *(ptr+left))
を
if(*(ptr+i) > *(ptr+left))
のように、判定条件を変更すると降順になります。今回のサンプルソースは昇順です。