【課題４−１２　再帰的関数（２）】
 再帰を用いてクイックソートによるソートのプログラムを，空欄Ａ〜Ｅを埋めて作成せよ．

#include <stdio.h>
#define N 8

void quick_sort(int *p, int left, int right);

int main(void) {
	int data[N] = {16, 41, 28, 33, 64, 2, 75, 59};
	int i;
	
	quick_sort(data, 0, N-1);
	
	for (i = 0; i < N; i++)
		printf("%d ", data[i]);
			
	return 0;
}

/* クリックソート */
/* 引数：	*p:並び替える配列の先頭要素のアドレス
			left:左端要素の添字 right:右端要素の添字
/* 返値： 	なし */
void quick_sort(int *p, int left, int right)
{
	int i, j, c, pivot, temp;
	
	c = (「　　Ａ　　」) / 2;	
	pivot = *(p+c);		//要素の中央を軸にする
	i = left; j = right;
	while (1) {
		//軸要素より左要素が小さい間ループして右に進む
		while (「　Ｂ　」< pivot)	
			i++;
		//軸要素より右要素が小さい間ループして左に進む
		while (pivot <「　Ｃ　」)
			j--;
		if (i >= j) //左右の添字が逆転するなら無限ループ終了
			break;
		//左右要素の入れ替え
		temp = *(p+i);
		*(p+i) = *(p+j);
		*(p+j) = temp;
		i++; j--;
	}
	if (left < i-1)	// まだ左側の要素があれば再帰呼び出し
		quick_sort(「　Ｄ　」);
	if (j+1 < right)	// まだ右側の要素があれば再帰呼び出し
		quick_sort(「　Ｅ　」);
}	


【実行結果】
	2 16 28 33 41 59 64 75 

【解説とヒント】
クイックソートは基本交換法や基本挿入法にくらべステップ数が少なくなるので，特にデータ量が多い場合に有効である．
クイックソートは，要素中のある値（中央位置の要素を取る場合が多い）を軸にし，要素を振り分けることを繰り返し，ソートを行う．具体的には，軸の左側に軸より小さな要素を配置し，軸の右側には軸より大きな要素を配置する．それを区間を小さくしながら再帰的に繰り返し，区間が一つになったら整列が完了している．