毎日1題--クイックソート20091016

問題の説明:高速ソートを実現し、pivotが複雑さに与える影響について議論してください.
問題分析:クイックソートは現在使用頻度の高いソート(もちろん、サボるために泡を立てることもある)であり、多くの参考書でpivotの選択は最初の要素を選択することであるが、高度ソートのシーケンスであれば時間の複雑さはO(n 2)に近づき、直接泡で完成するほうがよい.したがって,アルゴリズム全体の複雑さに及ぼす適切なPivotの選択の影響は極めて重要である.一般的にfront,rear,centerの間でpivotとして中間値を選択します.詳細な分析については、『Data Structure and Algorithm Analysis in C++Third Edition』P 206 7.2.2の分割戦略の議論を参照してください.
質問:
以下のプログラムは基本的にMark Allen Weissが提供する方法で実現されていますが、ソースプログラムはSTLを使用しており、10個以下のソートを挿入ソート完了に渡しているので、少し変更しました.

#include <stdio.h>

void QuickSort(int *a,int left,int right);
int median3(int *a,int left,int right);
void swap(int *a,int *b);
void swap3(int *a,int left,int right);

int main() {
	int n; // the amount of numbers to be sorted
	int i;
	int a[100];

	scanf("%d",&n);
	for (i = 0;i < n;i++)
		scanf("%d",&a[i]);
	QuickSort(a,0,n-1);
	for (i = 0;i < n;i++)
		printf("%d  ",a[i]);
	return 0;
}

void QuickSort(int *a,int left,int right) {
    if (left+3<=right) {
        int pivot = median3(a,left,right);
        int i = left,j = right-1;
        for (;;) {
            while (a[++i] < pivot) {}
            while (a[--j] > pivot) {}
            if (i < j)
                swap(&a[i],&a[j]);
            else
                break;
        }
        swap(&a[i],&a[right-1]);
        QuickSort(a,left,i-1);
        QuickSort(a,i+1,right);
    } else {
        swap3(a,left,right);
    }
}

void swap(int * a,int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

void swap3(int *a,int left,int right) {
	int center = (left+right) /2;
	if (a[center]<a[left])
		swap(&a[center],&a[left]);
	if (a[right]<a[left])
		swap(&a[right],&a[right]);
	if (a[center]>a[right])
		swap(&a[center],&a[right]);

}

int median3(int *a,int left,int right) {
	int center = (left+right)/2;
	if (a[center]<a[left])
		swap(&a[center],&a[left]);
	if (a[right]<a[left])
		swap(&a[left],&a[right]);
	if (a[center]>a[right])
		swap(&a[center],&a[right]);

	swap(&a[center],&a[right-1]);
	return a[right-1];
}