/*************************************/
/*     ソート（並べ替え）            */
/*          バブルソート             */
/*          選択ソート               */
/*          クイックソート           */
/*          バケツソート             */
/*               coded by Y.Suganuma */
/*************************************/
#include <stdio.h>

int ascend(int, int);
int descend(int, int);
void bubble(int, int *, int (*)(int, int));
void bucket(int, int *, int, int, int **, int *);
void quick(int, int *, int (*)(int, int));
void select(int, int *, int (*)(int, int));
void sort(int, int, int *, int (*)(int, int));
void sort(int, int *, int);
void swap(int *, int *);

int main()
{
	int i1, n, *data, sw;
					// データの入力
	printf("方法は（0:バブル, 1:選択, 2:クイック, 3: バケツ）？ ");
	scanf("%d", &sw);
	printf("データの数は？ ");
	scanf("%d", &n);

	data = new int [n];

	for (i1 = 0; i1 < n; i1++) {
		printf("   %d 番目のデータは？ ", i1+1);
		scanf("%d", &data[i1]);
	}
					// 昇順
	if (sw == 3)
		sort(n, data, 0);
	else
		sort(sw, n, data, ascend);

	printf("昇順\n  ");
	for (i1 = 0; i1 < n; i1++)
		printf(" %d", data[i1]);
	printf("\n");
					// 降順
	if (sw == 3)
		sort(n, data, 1);
	else
		sort(sw, n, data, descend);

	printf("降順\n  ");
	for (i1 = 0; i1 < n; i1++)
		printf(" %d", data[i1]);
	printf("\n");

	return 0;
}

/*********************************/
/*     データの比較（昇順）      */
/*     a > bの場合に０以外（真） */
/*********************************/
int ascend(int a, int b)
{
	return a > b;
}

/*********************************/
/*     データの比較（降順）      */
/*     a < bの場合に０以外（真） */
/*********************************/
int descend(int a, int b)
{
	return a < b;
}

/*****************************************/
/*     ２つのデータを交換する            */
/*          a,b : ２つのデータのアドレス */
/*****************************************/
void swap(int *a, int *b)
{
	int temp = *a;
	*a       = *b;
	*b       = temp;
}

/*******************************************/
/*     ソートの実行                        */
/*          method : ソート方法            */
/*                     =0 : バブルソート   */
/*                     =1 : 選択ソート     */
/*                     =2 : クイックソート */
/*          n : データの数                 */
/*          data : データ                  */
/*          compare : 比較を行う関数       */
/*******************************************/
void sort(int method, int n, int *data, int (*compare)(int, int))
{
	switch (method) {
		case 0:
			bubble(n, data, compare);
			break;
		case 1:
			select(n, data, compare);
			break;
		case 2:
			quick(n, data, compare);
			break;
		default:
			bubble(n, data, compare);
			break;
	}
}

/*******************************************/
/*     バケツソートの実行                  */
/*          n : データの数                 */
/*          data : データ                  */
/*          compare : =0 : 昇順            */
/*                    =1 : 降順            */
/*******************************************/
void sort(int n, int *data, int compare)
{
	int i1;

	int *num  = new int [10];
	int **bu   = new int * [10];
	for (i1 = 0; i1 < 10; i1++)
		bu[i1] = new int [n-1];

	bucket(n, data, compare, 1, bu, num);

	delete [] num;
	for (i1 = 0; i1 < 10; i1++)
		delete [] bu[i1];
	delete [] bu;
}

/****************************************************************/
/*     バブルソート                                             */
/*          n : データの数                                      */
/*          data : データ                                       */
/*          compare : 比較を行う関数                            */
/*     バブルソートの手順                                       */
/*　　　　　1)配列data[i]にn個のデータが入っているものとする．  */
/*　　　　　　　　i=0,1,･･･,n-1                                 */
/*　　　　　2)i番目のデータとi+1番目のデータを比較し，もし，    */
/*　　　　　　　　data[i+1] < data[i]　（昇順の場合）           */
/*　　　　　　であればそれらのデータを交換する．　i=0,1,･･･,n-2 */
/*　　　　　　　　→この結果，data[n-1]に最も大きなデータが入る */
/*                  ことになる                                  */
/*　　　　　3)次に，n-1個のデータに対し上の処理を繰り返す．     */
/*　　　　　4)同様に，n-2，n-3，・・・個のデータに対して同じ処理*/
/*            を繰り返す                                        */
/****************************************************************/
void bubble(int n, int *data, int (*compare)(int, int))
{
	int i1, sw = 0;

	if (n > 1) {
		for (i1 = 0; i1 < n-1; i1++) {
			if ((*compare)(data[i1], data[i1+1])) {
				sw = 1;
				swap(&data[i1], &data[i1+1]);
			}
		}
	}

	if (sw > 0)
		bubble(n-1, data, *compare);
}

/****************************************************************/
/*     選択ソート                                               */
/*          n : データの数                                      */
/*          data : データ                                       */
/*          compare : 比較を行う関数                            */
/*     選択ソートの手順                                         */
/*     （昇順の場合）．まず配列を走査して，最も小さな要素を見つ */
/*     けだす．見つけたら，それを配列の先頭要素と交換する．この */
/*     操作を配列の2番目の要素から始まるサブ配列について繰り返す*/
/****************************************************************/
void select(int n, int *data, int (*compare)(int, int))
{
	int i1, m;

	if (n > 1) {

		m = 0;
		for (i1 = 1; i1 < n; i1++) {
			if ((*compare)(data[m], data[i1]))
				m = i1;
		}

		if (m != 0)
			swap(&data[0], &data[m]);

		select(n-1, &data[1], *compare);
	}
}

/****************************************************************/
/*     クイックソート                                           */
/*          n : データの数                                      */
/*          data : データ                                       */
/*          compare : 比較を行う関数                            */
/*     クイックソートの手順                                     */
/*　　　　　　次のようなデータが与えられたとする．このとき，左端*/
/*            のデータ（ 37 ）を枢軸要素と呼び，個の要素がソート*/
/*            後の正しい位置にくるように以下の処理を行う（昇順の*/
/*            場合）．                                          */
/*　　　　　　　37  2  6  4  89  8  10  12  68  45              */
/*　　　　　1)配列の右端の要素から順に枢軸要素(37)と比較していき*/
/*            37より小さな要素があれば，その要素を37と交換する．*/
/*　　　　　　　12  2  6  4  89  8  10  37  68  45              */
/*　　　　　2)配列の左端（正確には，12の直後の要素）から順に枢軸*/
/*            要素(37)と比較していき，37より大きな要素があれば，*/
/*            その要素を37と交換する．                          */
/*　　　　　　　12  2  6  4  37  8  10  89  68  45              */
/*　　　　　3)配列の右端（正確には，89の直前の要素）から順に枢軸*/
/*            要素(37)と比較していき，37より小さな要素があれば，*/
/*            その要素を37と交換する．                          */
/*　　　　　　　12  2  6  4  10  8  37  89  68  45              */
/*　　　　　4)以上の結果，37の左には37より大きな要素はなく，また*/
/*            その右側には37より小さな要素は無い状態となる．つま*/
/*            り，37は，ソート後の正しい位置にあることがわかる．*/
/*　　　　　5)37の左側の配列（12  2  6  4  10  8），及び，右側の*/
/*            配列（89  68  45）に対して以上の処理を再帰的に繰り*/
/*            返す．                                            */
/****************************************************************/
void quick(int n, int *data, int (*compare)(int, int))
{
	int i1, left = 1, right = n-1, pos = 0, sw1 = 1, sw2;
/*
          枢軸要素を正しい位置に置く
*/
	while (sw1 > 0) {

		sw1 = 0;

		if (right-pos > 0) {
			sw2 = 0;
			for (i1 = right; i1 > pos && sw2 == 0; i1--) {
				if ((*compare)(data[pos], data[i1])) {
					swap(&data[pos], &data[i1]);
					sw1   = 1;
					sw2   = 1;
					pos   = i1;
					right = i1 - 1;
				}
			}
		}

		if (pos-left > 0) {
			sw2 = 0;
			for (i1 = left; i1 < pos && sw2 == 0; i1++) {
				if ((*compare)(data[i1], data[pos])) {
					swap(&data[pos], &data[i1]);
					sw1   = 1;
					sw2  = 1;
					pos  = i1;
					left = i1 + 1;
				}
			}
		}

		if (right-pos <= 0)
			sw1 = 0;
	}
/*
          サブ配列の処理
*/
	if (pos > 1)
		quick(pos, data, *compare);
	if (pos < n-2)
		quick(n-1-pos, &data[pos+1], *compare);
}

/****************************************************************/
/*     バケツソート                                             */
/*          n : データの数                                      */
/*          data : データ                                       */
/*          comp : 比較方法                                     */
/*                   =0 : 昇順                                  */
/*                   =1 : 降順                                  */
/*          k : 桁                                              */
/*          bu : バケツ                                         */
/*          num : 各バケツに入っているデータ数                  */
/*     バケツソートとは，一次元配列に入っているｎ個の正の整数を */
/*     バケツ配列と呼ばれる10×(n-1)の二次元配列を使用してソート*/
/*     する方法であり，以下に示すような手続きに従う．           */
/*　　　　　1)一次元配列の各数値を一の位に基づいてバケツ配列の対*/
/*            応する各行に格納する．たとえば，一次元配列の中に数*/
/*            値97，3，100がこの順序で入っていたとすると，97は行*/
/*            7，3は行3，100は行0に格納される．これを「分配パス */
/*            」と呼ぶ．                                        */
/*　　　　　2)バケツ配列の各行に格納されている値を行0から順番に */
/*            元の一次元配列の戻す．これを「収集パス」という．こ*/
/*            の時点で，一次元配列の中の値は100，3，97の順序にな*/
/*            る．                                              */
/*　　　　　3)以上の処理を数値の各位について繰り返す．          */
/****************************************************************/
void bucket(int n, int *data, int comp, int k, int **bu, int *num)
{
	int i1, i2, k1, kk = 1, sw1 = 1, sw2 = 0;
/*
     準備
*/
	for (i1 = 0; i1 < k-1; i1++)
		kk *= 10;
	for (i1 = 0; i1 < 10; i1++)
		num[i1] = 0;
/*
     分配パス
*/
	for (i1 = 0; i1 < n; i1++) {
		if (data[i1] >= 10*kk)
			sw2 = 1;
		k1 = (data[i1] / kk) % 10;
		if (num[k1] >= n-1)
			sw1 = 0;
		else {
			bu[k1][num[k1]] = data[i1];
			num[k1]++;
		}
	}
/*
     収集パス
*/
	if (sw1 > 0) {
		k1 = 0;
		if (comp == 0) {
			for (i1 = 0; i1 < 10; i1++) {
				for (i2 = 0; i2 < num[i1]; i2++) {
					data[k1] = bu[i1][i2];
					k1++;
				}
			}
		}
		else {
			for (i1 = 9; i1 >= 0; i1--) {
				for (i2 = 0; i2 < num[i1]; i2++) {
					data[k1] = bu[i1][i2];
					k1++;
				}
			}
		}
	}
/*
     次の桁
*/
	if (sw2 > 0)
		bucket(n, data, comp, k+1, bu, num);
}