import java.util.*;

class InsertSort extends Thread{
	private int[] a;
	Object obj;
	public InsertSort(int[] a,Object obj){
		this.a=a;
		this.obj=obj;
	}
	public void run(){
		synchronized(obj){
		    long time=System.currentTimeMillis();
		    int j;
  	    	for(int i=2;i<a.length;i++){
  	            if(a[i]<a[i-1]){ //需要將a[i]插入有序子表中
  		           a[0]=a[i];    //復制為哨兵
  		           a[i]=a[i-1];
  		           for( j=i-2;a[0]<a[j];j--)
  		              a[j+1]=a[j];    //記錄后移
  		           a[j+1]=a[0];       //插入到正確位置
  		        }
  		
  	        }
  	        time=System.currentTimeMillis()-time;
  	        System.out.println("Use insert sort,the time is:"+time+"ms");
  	        System.out.println("After insert sort,the sorted array is:"); //打印排序數組   
            for(int i=1;i<a.length;i++)
               System.out.print(a[i]+" ");
            System.out.println();
		}
	}
	
	public static void main(String args[]){		
         Object obj=new Object();         
         Random r=new Random();
         int size=10;//數組個數      
         int randomArray1[]=new int[size];   //定義一個隨機數組
         int randomArray2[]=new int[size];     //定義一個排序數組
    
         //生成兩個同樣的隨機數組
         for(int i=1;i<size;i++)
              randomArray1[i]=r.nextInt()%1000;   //在隨機數組中存入隨機數
         for(int i=1;i<size;i++)
              randomArray2[i]=randomArray1[i];
         
         //打印隨機數組         
         System.out.println("The random array is:");    
         for(int i=1;i<size;i++)
         System.out.print(randomArray1[i]+" ");
         System.out.println();
         
         (new InsertSort(randomArray1,obj)).start();
         (new BubbleSort(randomArray2,obj)).start();
		
	}
}

class BubbleSort extends Thread{
	private int[] a;
	Object obj;
	public BubbleSort(int[] a,Object obj){
		this.a=a;
		this.obj=obj;
	}
	public void run(){
		synchronized(obj){
		    long time=System.currentTimeMillis();
		    int temp,j;  	
  	        for(j=a.length-1;j>1;j--){  	
  	            for(int i=1;i<a.length-1;i++){
  		           if(a[i]>a[i+1]){
  			           temp=a[i];
  			           a[i]=a[i+1];
  			           a[i+1]=temp;
  	               }
  	            }
  	        }
  	        time=System.currentTimeMillis()-time;
  	        System.out.println("Use bubble sort,the time is:"+time+"ms");
  	        
  	        System.out.println("After bubble sort,the sorted array is:"); //打印排序數組   
            for(int i=1;i<a.length;i++)
               System.out.print(a[i]+" ");
            System.out.println();
		}
	}
}