/* ソートの実行時間測定の例 */
import java.util.*;
class Foo {
    public static void main (String[] args) {
	int size=10000, seed=3885;
	int[] data = make_array(size, seed);

	long start = System.currentTimeMillis(); // 開始時刻
	bubble_sort(data);    	      	         // 配列データをバブルソート
	long end = System.currentTimeMillis();   // 終了時刻
	System.out.println(end-start);           // 時刻の差を表示

        // print_array(data);                   // ソート結果を表示
        if (!is_sorted_array(data)) {        // ソート結果をチェック
            System.out.println("bad sorted");
        }
    }

    // 配列中の2つのデータ data[i]と data[j]の値を交換する．
    static void swap (int[] data, int i, int j) {
        int tmp=data[i]; data[i]=data[j]; data[j]=tmp;
    }

    static int[] make_array (int size, long seed) {
        Random random = new Random(seed);
        int[]  data = new int[size];

        for (int i=0; i<data.length; i++) {
            // 0〜size-1 の範囲でランダムにデータを生成
            data[i] = Math.abs(random.nextInt()) % size;
        }
        return data;
    }

    // 整数配列の中身を表示するメソッド．ソートの様子を知るのに便利．
    static void print_array (int[] data) {
        for (int i=0; i<data.length; i++) {
            System.out.print(data[i]+" ");
        }
        System.out.println(); // 改行する
    }

    // 整数配列 dataが昇順ならば true，さもなくば falseを返すメソッド．
    // データ数が多い時に，ソート結果をチェックするのに便利．
    static boolean is_sorted_array(int[] data) {
        for (int i=0; i<data.length-1; i++) {
            if (data[i]>data[i+1]) {
                return false;
            }
        }
        return true;
    }

    static void bubble_sort(int[] data) {
	for (int i=data.length-1; i>0; i--) {
	    for (int j=0; j<i; j++) {
		if (data[j] > data[j+1]) {
    	    	    swap(data, j, j+1);
		}
	    }
	}
    }
}