/*************************************/
/*     ソート（並べ替え）            */
/*          バブルソート             */
/*          選択ソート               */
/*          クイックソート           */
/*          バケツソート             */
/*               coded by Y.Suganuma */
/*************************************/
import java.io.*;

public class Test {
	public static void main(String args[]) throws IOException
	{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int i1, n, data[], sw;
					// データの入力
		System.out.print("方法は（0:バブル, 1:選択, 2:クイック, 3: バケツ）？ ");
		sw = Integer.parseInt(in.readLine());
		System.out.print("データの数は？ ");
		n = Integer.parseInt(in.readLine());

		data = new int [n];

		for (i1 = 0; i1 < n; i1++) {
			System.out.print("   " + (i1+1) + " 番目のデータは？ ");
			data[i1] = Integer.parseInt(in.readLine());
		}

		Compare st = new Compare ();
					// 昇順
		st.sort(n, data, sw, 0);

		System.out.print("昇順\n  ");
		for (i1 = 0; i1 < n; i1++)
			System.out.print(" " + data[i1]);
		System.out.print("\n");
					// 降順
		st.sort(n, data, sw, 1);

		System.out.print("降順\n  ");
		for (i1 = 0; i1 < n; i1++)
			System.out.print(" " + data[i1]);
		System.out.print("\n");
	}
}

----------------------------------------------

/********************/
/*     データの比較 */
/********************/
class Compare extends Sort
{
	/*********************************/
	/*     データの比較（昇順）      */
	/*     a > b の場合に真          */
	/*********************************/
	boolean ascend(int a, int b)
	{
		return a > b;
	}

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

------------------------------------------

/********************/
/*     ソートの実行 */
/********************/
class Sort {

	boolean ascend(int a, int b) {return true;}
	boolean descend(int a, int b) {return true;}

	/*************************************/
	/*     ２つのデータを交換する        */
	/*          data : データ            */
	/*          i,j : ２つのデータの位置 */
	/*************************************/
	void swap(int data[], int i, int j)
	{
		int temp = data[i];
		data[i]  = data[j];
		data[j]  = temp;
	}

	/***********************************************/
	/*     ソートの実行                            */
	/*          n : データの数                     */
	/*          data : データ                      */
	/*          method : ソート方法                */
	/*                     =0 : バブルソート       */
	/*                     =1 : 選択ソート         */
	/*                     =2 : クイックソート     */
	/*                     =3 : バケツソート       */
	/*          cmp : ソート方向（0:昇順，1:降順） */
	/***********************************************/
	void sort(int n, int data[], int method, int cmp)
	{
		switch (method) {
			case 0:
				bubble(n, data, cmp);
				break;
			case 1:
				select(0, n, data, cmp);
				break;
			case 2:
				quick(0, n-1, data, cmp);
				break;
			case 3:
				int num[]  = new int [10];
				int bu[][] = new int [10][n-1];
				bucket(n, data, cmp, 1, bu, num);
				break;
			default:
				bubble(n, data, cmp);
				break;
		}
	}

	/****************************************************************/
	/*     バブルソート                                             */
	/*          n : データの数                                      */
	/*          data : データ                                       */
	/*          cmp : ソート方向（0:昇順，1:降順）                  */
	/*     バブルソートの手順                                       */
	/*　　　　　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 cmp)
	{
		int i1, sw = 0;
		boolean bl;

		if (n > 1) {
			for (i1 = 0; i1 < n-1; i1++) {
				bl = (cmp == 0) ? ascend(data[i1], data[i1+1]) :
                                  descend(data[i1], data[i1+1]);
				if (bl) {
					sw = 1;
					swap(data, i1, i1+1);
				}
			}
		}

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

	/****************************************************************/
	/*     選択ソート                                               */
	/*          k : 開始位置                                        */
	/*          n : データの数                                      */
	/*          data : データ                                       */
	/*          cmp : ソート方向（0:昇順，1:降順）                  */
	/*     選択ソートの手順                                         */
	/*     （昇順の場合）．まず配列を走査して，最も小さな要素を見つ */
	/*     けだす．見つけたら，それを配列の先頭要素と交換する．この */
	/*     操作を配列の2番目の要素から始まるサブ配列について繰り返す*/
	/****************************************************************/
	void select(int k, int n, int data[], int cmp)
	{
		int i1, m;
		boolean bl;

		if (k < n-1) {

			m = k;
			for (i1 = k+1; i1 < n; i1++) {
				bl = (cmp == 0) ? ascend(data[m], data[i1]) :
                                  descend(data[m], data[i1]);
				if (bl)
					m = i1;
			}

			if (m != k)
				swap(data, k, m);

			select(k+1, n, data, cmp);
		}
	}

	/****************************************************************/
	/*     クイックソート                                           */
	/*          k1,k2 : 開始位置と終了位置                          */
	/*          data : データ                                       */
	/*          cmp : ソート方向（0:昇順，1:降順）                  */
	/*     クイックソートの手順                                     */
	/*　　　　　　次のようなデータが与えられたとする．このとき，左端*/
	/*            のデータ（ 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 k1, int k2, int data[], int cmp)
	{
		int i1, left = k1+1, right = k2, pos = k1, sw1 = 1, sw2;
		boolean bl;
/*
          枢軸要素を正しい位置に置く
*/
		while (sw1 > 0) {

			sw1 = 0;

			if (right-pos > 0) {
				sw2 = 0;
				for (i1 = right; i1 > pos && sw2 == 0; i1--) {
					bl = (cmp == 0) ? ascend(data[pos], data[i1]) :
    	                              descend(data[pos], data[i1]);
					if (bl) {
						swap(data, pos, i1);
						sw1   = 1;
						sw2   = 1;
						pos   = i1;
						right = i1 - 1;
					}
				}
			}

			if (pos-left > 0) {
				sw2 = 0;
				for (i1 = left; i1 < pos && sw2 == 0; i1++) {
					bl = (cmp == 0) ? ascend(data[i1], data[pos]) :
    	                              descend(data[i1], data[pos]);
					if (bl) {
						swap(data, pos, i1);
						sw1  = 1;
						sw2  = 1;
						pos  = i1;
						left = i1 + 1;
					}
				}
			}

			if (right-pos <= 0)
				sw1 = 0;
		}
/*
          サブ配列の処理
*/
		if (pos-k1 > 1)
			quick(k1, pos-1, data, cmp);
		if (k2-pos > 1)
			quick(pos+1, k2, data, cmp);
	}

	/****************************************************************/
	/*     バケツソート                                             */
	/*          n : データの数                                      */
	/*          data : データ                                       */
	/*          cmp : ソート方向（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 cmp, 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 (cmp == 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, cmp, k+1, bu, num);
	}
}