/***************************************************************/
/* 2007-05-12 Defolos quicksort:main                           */
/*                                                             */
/* クイックソートを行う                                        */
/* オプションに「-d」を指定すると降順に表示する                */
/***************************************************************/
#include <stdio.h>
#include <string.h>

#define WEEK 7

/*-------------------------------------------------------------*/
/* プロトタイプ宣言 */
/*-------------------------------------------------------------*/
void input_data(double *data, int length);
int quicksort(double *data, int i, int j);
int get_pivot(double *data, int i, int j);
int divide(double *data, int i, int j, double temp);
void swap(double *data, int i, int j);


/*=============================================================*/
/* メイン関数始まり */
/*=============================================================*/
int main(int argc, char *argv[]){

/*-------------------------------------------------------------*/
/* 変数の宣言 */
/*-------------------------------------------------------------*/
	double data[WEEK];
	int lc;

/*-------------------------------------------------------------*/
/* データの入力 */
/*-------------------------------------------------------------*/
	input_data(&data[0], WEEK);

/*-------------------------------------------------------------*/
/* ソート前のデータ配列の表示 */
/*-------------------------------------------------------------*/
	printf("\n_____[Before sort]_____\n");
	for(lc=0; lc<WEEK; lc++){
		printf("%f ", data[lc]);
	}printf("\n\n");

/*-------------------------------------------------------------*/
/* quicksort関数の呼び出し */
/*-------------------------------------------------------------*/
	quicksort(&data[0], 0, WEEK-1);

/*-------------------------------------------------------------*/
/* パラメタ処理 */
/*-------------------------------------------------------------*/
	int i=1, header=0;
	if(argc > 1){
		while(i < argc){
			if(strncmp(argv[i], "-d", 1) == 0){
				header = 1;
			}
			i++;
		}
	}

/*-------------------------------------------------------------*/
/* ソート結果の出力 */
/*-------------------------------------------------------------*/
	switch(header){

		case 0:
			printf("_____[After sort]_____\n");
			for(lc=0; lc<WEEK; lc++){
				printf("%f ", data[lc]);
			}
			printf("\n");
			break;

		case 1:
			printf("_____[After sort]_____\n");
			for(lc=WEEK-1; lc>=0; lc--){
				printf("%f ", data[lc]);
			}
			printf("\n");
			break;
	}

	return 0;
}

/***************************************************************/
/* 2007-05-12 Defolos quicksort:input_data                     */
/*                                                             */
/* キーボードからのデータ入力を配列に格納する                  */
/***************************************************************/
void input_data(double *data, int length){

	int i=0;
	while(i < length){
		printf("%d: ", i+1);
		scanf("%lf", data);
		data++, i++;
	}
}

/***************************************************************/
/* 2007-05-12 Defolos quicksort:quicksort                      */
/*                                                             */
/* クイックソートを行う                                        */
/* データが格納された配列、並び替えたい要素のはじめの添え字、  */
/* 最後の添え字を引数としてとる 再帰アルゴリズムを用いている   */
/***************************************************************/
int quicksort(double *data, int i, int j){

	if(i == j){
		return 0;
	}
	int pivot, k;
	pivot = get_pivot(&data[0], i, j);
	if(pivot != -1){
		k = divide(&data[0], i, j, *(data+pivot));
		quicksort(&data[0], i, k-1);
		quicksort(&data[0], k, j);
	}
}

/***************************************************************/
/* 2007-05-12 Defolos quicksort:get_pivot                      */
/*                                                             */
/* ピボットの要素の添え字を得る                                */
/* 渡されたデータのij要素のうち大きいほうをピボットとして返す  */
/* データ中の要素が同じ数値であれば-1を返す                    */
/***************************************************************/
int get_pivot(double *data, int i, int j){

	int k = i+1;
	while(k<=j && *(data+i) == *(data+k)){
		k++;
	}
	if(k > j){
		return -1;
	}
	if(*(data+i) >= *(data+k)){
		return i;
	}
	return k;
}

/***************************************************************/
/* 2007-05-12 Defolos quicksort:divide                         */
/*                                                             */
/* ソート対象範囲を分割して更新する                            */
/* ピボットよりも小さいグループと大きいグループに分ける        */
/* ピボットよりも大きいグループの開始添え字を戻り値とする      */
/***************************************************************/
int divide(double *data, int i, int j, double temp){

	int left = i, right = j;
	while(left <= right){
		while((left <= j) && (*(data+left) < temp)){
			left++;
		}
		while((right >= i) && (*(data+right) >= temp)){
			right--;
		}
		if(left > right){
			break;
		}
		swap(&data[0], left, right);
		left++, right--;
	}
	return left;
}

/***************************************************************/
/* 2007-05-12 Defolos quicksort:swap                           */
/*                                                             */
/* 要素の値の交換を行う                                        */
/***************************************************************/
void swap(double *data, int i, int j){

	double temp;
	temp = *(data+i);
	*(data+i) = *(data+j);
	*(data+j) = temp;
}