/* インサートソート */
import java.util.*;
class InsertSort {
    public static void main (String[] args) {
        int   seed = 3885;                   // 擬似乱数の種
        int   size = 1000;                   // 配列の大きさ
        int[] data = make_array(size, seed); // 配列データを作成

    	insert_sort(data);    	      	     // 配列データをインサートソート
        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;
    }

    // 整数の大きさ sizeの配列をつくり，種を seedとした
    // 擬似乱数で初期化する．種が同じならば同じデータ列となる．
    // この配列をソートするデータ列として使用する．
    // sizeで割った余りとしているのは，重複データを作るためである．
    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 insert_sort (int[] data) {
	for (int i=1; i<data.length; i++) {
	    for (int j=i; j>0 && data[j-1]>data[j]; j--) {
		swap(data, j-1, j);
	    }
	}
    }
}