C言語アルゴリズム-クイックソート
クイックソート（quick sort）とは
クイックソート（quick sort）
クイックソートとは、1962年にCharles Antony.A.R.Hoareが発表した、分割統治アプローチ（大きな問題を複数の小さな問題に分割して各個解決する）の整列アルゴリズムです。
基準とする要素より小さい要素グループと大きい要素グループに分割する作業を繰り返すことで整列を行います。
クイックソートの処理の流れは以下の通りです。
- ある一つの適当な要素を選び出し、最終的に置かれるべき位置へ移動する。この要素を「枢軸(pivot)」と呼ぶ。
- 枢軸より大きな要素は右側へ、小さな要素は左側に置き、２つの部分配列を作成（partition）する。
- 部分配列がただ１つの要素になるまで、クイックソートのアルゴリズムを適用して分割を繰り返す。
以上、全ての分割が終るとソートが完了しています。
クイックソートの整列過程
[before]:6 1 4 2 3 7 5
---------[1 round]---------
[array]:6 1 4 2 3 7 5
[pivot] = 5
[swap] (left=6) <-> (right=5)
[array]:(5 1 4 2 3) (7 6)
---------[2 round]---------
[array]:5 1 4 2 3
[pivot] = 4
[swap] (left=5) <-> (right=3)
[swap] (left=4) <-> (right=2)
[array]:(3 1 2) (4 5)
---------[3 round]---------
[array]:3 1 2
[pivot] = 2
[swap] (left=3) <-> (right=2)
[array]:(2 1) (3)
---------[4 round]---------
[array]:2 1
[pivot] = 2
[swap] (left=2) <-> (right=1)
[array]:(1) (2)
---------[5 round]---------
[array]:(4 5)
[pivot] = 4
[swap] (left=4) <-> (right=4)
[array]:(4) (5)
---------[6 round]---------
[array]:(7 6)
[pivot] = 7
[swap] (left=7) <-> (right=6)
[array]:(6) (7)
==============================
[after] :1 2 3 4 5 6 7
クイックソートの性能
クイックソートは内部整列では最速のアルゴリズムといわれており、平均計算量が「O(n log n)」です。しかし、ピボットの選択を間違えた場合などはバブルソートと同等の処理内容になってしまうため、最悪計算量が「O(n ^ 2)」となります。要素が少ない場合には、クイックソートよりも選択ソートの方が速いこともあります。
ピボットの選択
ピボットの選択を間違えた場合、計算量は最悪の「O(n ^ 2)」となります。
効率の悪いピボットを選ぶ可能性を排除するため、配列から3つほどデータを取り出して、その中央値をピボットに選ぶという「median-of-three」という手法がよく用いられます。
qsort()関数について
標準ライブラリにはqsort()関数がクイックソートを行う処理として用意されています。自作してバグを内臓するよりは、まずはqsort()を用いることができるかどうか検討したほうが賢明です。
C言語によるクイックソートのプログラム
再起処理で実装したクイックソートは実装が簡単ですが、データ量が多い場合にスタック不足でエラーとなることがあります。そのような場合には、スタックを用いて非再起処理のクイックソートを実装するなどの工夫を行う必要があります。
非再起版のクイックソートと再起版のクイックソートを以下に記述します。
#include <stdio.h>
#include <stdlib.h>
#include <stdlib.h>
#include <time.h>
#define STACK_SIZE 32
/*!
* @brief 配列にランダムな数値を格納する。
* @param[out] array 数値格納先の配列
* @param[in] size 配列のサイズ
*/
static void
array_random_number(int *array, unsigned int size)
{
int i;
/* 起動毎に異なる乱数を発生させる */
srand((unsigned int)time(NULL));
for(i = 0; i < size; i++){
array[i]=rand();
}
}
/*!
* @brief 配列内容を表示する
* @param[in] array 数値格納先の配列
* @param[in] size 配列のサイズ
*/
static void
array_print(int *array, unsigned int size)
{
int i = 0;
for(i = 0; i < size; i++){
printf("%d ", array[i] );
}
putchar('\n');
}
/*!
* @brief 要素要素を入れ替える
* @param[in] i 要素位置
* @param[in] j 要素位置
*/
static void
swap(int *i, int *j)
{
int temp;
temp = *i;
*i = *j;
*j = temp;
}
/*!
* @brief 枢軸の値を取得する。
* @param[in/out] array 整列する要素配列
* @param[in] left 配列の左端
* @param[in] right 配列の右端
* @return 枢軸の添え字
* @note 左端、中央、右端の中央値を枢軸とする。
*/
static int
get_pivot(int array[], int left, int right)
{
int x, y, z;
int center = (right + left) / 2;
x = array[center];
y = array[left];
z = array[right];
if((x <= y && y <= z)||(z <= y && y <= x)) return(y);
if((x <= z && z <= y)||(y <= z && z <= x)) return(z);
return(x);
}
/*!
* @brief 配列を分割する
* @param[in/out] array 整列する要素配列
* @param[in] left 配列の左端
* @param[in] right 配列の右端
* @return 分割位置
*/
static int
partition(int array[], int left, int right)
{
int pivot_val;
/* 枢軸の値を取得する */
pivot_val = get_pivot(array, left, right);
while(left <= right){
/* 枢軸より大きな要素が見つかるまでポインタを右へ進める */
while(array[left] < pivot_val) left++;
/* 枢軸より小さな要素が見つかるまでポインタを左へ進める */
while(array[right] > pivot_val) right--;
/* 要素を交換する */
if(left <= right){
swap(&array[left], &array[right]);
left++;
right--;
}
}
return(left);
}
/*!
* @brief 再帰処理でクイックソートを行う。
* @param[in/out] array 整列する要素配列
* @param[in] size 配列のサイズ
*/
void
recursive_quick_sort(int array[], unsigned int size)
{
int pivot = 0;
int left = 0;
int right = size - 1;
/* 部分配列がただ一つになれば処理を終了する */
if(size <= 1) return;
/* 枢軸を基準として分割する */
pivot = partition(array, left, right);
/* 左右の部分配列をそれぞれクイックソートする */
recursive_quick_sort(array, pivot);
recursive_quick_sort(array + pivot, size - pivot);
}
/*!
* @brief クイックソートを行う。
* @param[in/out] array 整列する要素配列
* @param[in] size 配列のサイズ
*/
void
quick_sort(int array[], unsigned int size)
{
int pivot;
int left, right;
int low_stack[STACK_SIZE];
int high_stack[STACK_SIZE];
int sp = 1; /* スタックポインタ */
/* スタックを初期化する */
low_stack[0] = 0;
high_stack[0] = size - 1;
while(sp > 0){
/* スタックから整列する範囲の添字を取り出す */
sp--;
left = low_stack[sp];
right = high_stack[sp];
if(left < right){
/* 枢軸を基準として分割する */
pivot = partition(array, left, right);
/* 右側の部分配列位置をスタックに記憶する */
low_stack[sp] = pivot;
high_stack[sp] = right;
sp++;
/* 左側の部分配列位置をスタックに記憶する */
low_stack[sp] = left;
high_stack[sp] = pivot - 1;
sp++;
}
}
}
int
main(void)
{
//int buf[] = {9,4,2,3,8,5,1,10,0,7,6};
int buf[1000];
array_random_number(buf, sizeof(buf)/4);
printf("[before]:"); array_print(buf, (sizeof(buf)/4));
quick_sort(buf, (sizeof(buf)/4));
printf("[after] :"); array_print(buf, (sizeof(buf)/4));
return( 0 );
}
関連ページ
- C言語
- C言語アルゴリズム-クイックソート
- C言語アルゴリズム-シェルソート
- C言語アルゴリズム-マージソート
- C言語アルゴリズム-ヒープソート
- C言語アルゴリズム-バブルソート
- C言語アルゴリズム-ビンソート
- C言語アルゴリズム-ボゴソート
- C言語アルゴリズム-基数ソート
- C言語アルゴリズム-選択ソート
- C言語アルゴリズム-挿入ソート
- C言語アルゴリズム-分布数え上げソート