Ｃ言語のクイックソートについて

[shin]

このプログラムの基準値は一番右端の値になっているのですが、基準値を右端左端中央値から考えた値にするにはどうすればいいのか教えてください。

コード:

#include <stdio.h>
#include <time.h>

int x[10000000];

// Exchanging i-th value and j-th value
void swap(i,j){
	int tmp;
	tmp=x[i];
	x[i]=x[j];
	x[j]=tmp;
}

// Decision of the median between left and right
int median(left,right){
	int mid, i;
	mid=(left+right)/2;
	if(x[left]>x[mid]) swap(left, mid);
	if(x[mid]>x[right]) swap(mid, right);
	if(x[left]>x[mid]) swap(left, mid);
	swap(mid,right);
}

int divide(int start, int end)
{
	int i,j,k,pivot,tmp;
	median(start,end);
	pivot=end;
	i=start;
	j=end-1;
	while(1){
		while(x[i] < x[pivot]) i=i+1;
		while(x[pivot] < x[j] && j>i) j=j-1;
		if(j<=i) break;
		tmp=x[i];
		x[i]=x[j];
		x[j]=tmp;
		i=i+1;
		j=j-1;
	}
	tmp=x[i];
	x[i]=x[pivot];
	x[pivot]=tmp;
	return i;
}
void quick_sort(int start, int end)
{
	int s;
	if(end<=start) return;
	s=divide(start, end);
	quick_sort(start, s-1);
	quick_sort(s+1, end);
}


main ()
{
	int i, j, n;
	int iseed, icount, tmpdata;
	double time, timerstart, timerend;
	printf("Quick sort program.\n");
/* random number seed */
	printf("Please input the seed: ");
	scanf("%d", &iseed);
	for(j=1; j<=10; j=j+2){
		n=j*1000000;
		icount=0;
/* random number junbi */
		srand(iseed+j);
/* Throwing away first 10 random numbers */
		for(i=1; i<10; i=i+1) {rand();}
/* Data creation */
		while(icount<n){
			tmpdata=rand();
			if(tmpdata>100000000){
				x[icount]=tmpdata;
				icount=icount+1;
			}
		}
/*
		for(i=1;i<n;i=i+1){printf("%d\n",x[i]);}
*/		
		quick_sort(0, n-1);
		timerstart=clock();
		quick_sort(0, n-1);
		timerend=clock();
		time=(timerend-timerstart)/CLOCKS_PER_SEC;
		printf("%d \t %f\n",n,time);
	}
	return 0;
}

[ookami]

プログラム全体の流れと、各変数の意味を簡単に説明してもらってよろしいでしょうか？

特に、
> このプログラムの基準値は一番右端の値
が、ソースコード上のどこなのか、あたりが重要だと思います。

あと、
> 基準値を右端左端中央値から考えた値にする
は、意味がよく分からないので補足をお願いします。

質問の書き方については、上記「フォーラムルール」もご参考下さい。

[Dixq (管理人)]

> shinさん

ピボットにセットする値を変えれば基準値を変更する事が出来ますよね。
現在はここで
pivot=end;
セットしているわけですから、どうすればいいか予想できそうです。
クイックソートについてはこちらのアプリで学習できるのでよろしければ参考にどうぞ
http://dixq.net/sort.html