import java.util.Locale; //for nanoTime

/**
 * This program demonstrates & times various sorting algorithms.
 *
 * @author Dave Slemon
 * @version v100
 */
class Main
{

    
    
        public static void main(String[] args)
        { //main
            
            int MAXSIZE = 30000;        
            int A[] = new int[MAXSIZE];  //array to be sorted
            int n = MAXSIZE;
           
            
            //populating the array A with random numbers
            for(int i = 0; i < MAXSIZE; i++)
                A[i] = getRandom(1000);
              
                
            //start timer    
            long start = System.nanoTime();    
            
            bubbleSort( A, n ); 
           
        
            //end timer
            long finish = System.nanoTime();
            double elapsedTime = (double)( (finish - start) / 1E9 );
            
                
            printArray(A, n);
            System.out.println("\nSort time was: " + elapsedTime + " secs");
            
        } //main
        
        
        
        
        /*
         * This routine prints an array, with 20 numbers
         * per line
         */
        public static void printArray(int[] A, int n)
        { //print
            int count = 1;
            for(int j=0; j < n; j++)
            {
                System.out.print ( A[j] + " ");
                if (count++ % 20 == 0) System.out.println();
            }
            
        } //print
        
        
        
        
      
        
        /**
         * Provides a random int between 0 and max, 
         * not including max
         * @return 0 <= num < max 
        */
       public static int getRandom(int max)
       { //getRandom
           return (int)(Math.random() * max);
        } //getRandom
        
        
        
        
        
        
        /**
               * bubbleSort uses the bubble sort algoithm to sort an array of integers
               *
               * @author Dave Slemon
               * @version 1.0 March 22, 2021
               *
               * @param A is an array of integers to be sorted
               * @param n is the number elements to sort from the beginning
               *
               * @return A of integers sorted in ascending order
        */  
        public static void bubbleSort(int[] A, int n) 
        { //bubble 
        
        int temp = 0;  
         for(int i=0; i < n; i++)
         {  
                 for(int j=1; j < (n-i); j++)
                 {  
                          if(A[j-1] > A[j]){  
                                 //swap elements  
                                 temp = A[j-1];  
                                 A[j-1] = A[j];  
                                 A[j] = temp;  
                         }  
                          
                 }  
          }
          
        } //bubble

        
        
              
        
        
        /**
               * bubbleSort uses the bubble sort algoithm to sort an array of integers
               *
               * @author Dave Slemon
               * @version 1.0 March 22, 2021
               *
               * @param A is an array of string to be sorted
               * @param n is the number of items in the array to sort
               *
               * @return A of strings sorted in ascending order
        */  
        public static void bubbleSort(String[] A, int n) 
        { //bubble 
       
        String temp = "";  
         for(int i=0; i < n; i++)
         {  
                 for(int j=1; j < (n-i); j++)
                 {  
                          if(  A[j-1].compareTo( A[j] ) > 0)
                          {  
                                 //swap elements  
                                 temp = A[j-1];  
                                 A[j-1] = A[j];  
                                 A[j] = temp;  
                         }  
                          
                 }  
          }
          
        } //bubble
        
        
 
        
        
        
}