// BucketSort	バケットソート bucket sort
//								2019.06.14
//								2007.05.18
//								by M.Yanaka

class BucketSort {
	public static void main(String[] args)
	{
	    int[] x = new int[] {4, 2, 9, 1};	/* 配列の宣言と初期化 */

	    System.out.println("ソーティング実行前");
	    for (int i = 0; i < x.length; i++)
		System.out.println("No." + (i+1) + " : " + x[i]);

	    bucket_sort(x, 10);

	    System.out.println("ソーティング実行後");
	    for (int i = 0; i < x.length; i++)
		System.out.println("No." + (i+1) + " : " + x[i]);
	}

	public static void bucket_sort(int[] x, int max)
	{
	    int[] y = new int[max + 1];		/* 作業用配列 */
	    int     i, k;			/* 作業用 */
	
	    for (k = 0; k <= max; k++)
	        y[k] = 0;
	    for (i = 0; i < x.length; i++)
		y[x[i]] = 1;
	    i = 0;
	    for (k = 0; k <= max; k++)
		if (y[k] > 0)
		    x[i++] = k;	
	}
}