高速並べ替えの原理とC実現

概要
高速ソートは再帰原理を用いて実現される一般的なソートアルゴリズムであり,本稿では高速ソートを用いて配列をソートすることを紹介する.
配列が空であるか、または1つの要素だけがソートする必要がないため、高速ソート再帰のベースライン条件は配列長が2未満である.
きほんげんり
まず、配列から基準値(pivot)と呼ばれる要素を選択します.次に、ベース準値より小さい要素と、ベース準値より大きい要素を見つけます.このプロセスをパーティション(partioning)と呼びます.パーティションを行った後、得られた2つのサブ配列は無秩序です.
例えば対数グループ
5
2
4
1
3
最後の要素3を選択して基準値としてパーティション化
2
1
3
5
4
次のようになります.

基準値より小さいすべてのサブ配列

基準値

は、基準値より大きいすべてのサブ配列からなる.

2つのサブ配列を再帰的に操作します.
C言語のクイックソート例

#include 
#include 
#include 

void myswap(void *a, void *b, size_t width)
{
	char tmp;
	int i;
	for (i = 0; i < width; i++){
		tmp = *((char*)a + i);
		*((char*)a + i) = *((char*)b + i);
		*((char*)b + i) = tmp;
	}
}

int partitioning(int *arr, int l, int r)
{
	//              
	int pivot = arr[r];

	//          
	int last_less_idx = l - 1;

	for (int i = l; i < r; i++){
		if (arr[i] < pivot){
			last_less_idx++;
			myswap(&arr[i], &arr[last_less_idx], sizeof(int));
		}
	}

	//                  
	myswap(&arr[last_less_idx + 1], &arr[r], sizeof(int));

	//           
	return last_less_idx + 1;
}

void myqsort(int *arr, int l, int r)
{
	int partition_idx;
	if (l >= r)
		return;

	partition_idx = partitioning(arr, l, r);
	myqsort(arr, l, partition_idx - 1);
	myqsort(arr, partition_idx + 1, r);
}

void show_arr(int *arr, int l, int r)
{
	for (int i = l; i <= r; i++){
		printf("%d ", arr[i]);
	}
}

int main(int argc, char* argv[])
{

	int arr[10];
	int i;

	srand(time(NULL));
	for (i = 0; i < 10; i++){
		arr[i] = rand() % 100;
	}

	printf("show array before qsort
");
	show_arr(arr, 0, 9);

	myqsort(arr, 0, 9);
	printf("
show array after qsort
");
	show_arr(arr, 0, 9);

	return 0;
}