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
            
           
            
            //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 ); 
            quickSort(A, 0, A.length-1) ;
        
            //end timer
            long finish = System.nanoTime();
            double elapsedTime = (double)( (finish - start) / 1E9 );
            
                
            printArray(A);
            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)
        { //print
            int count = 1;
            for(int j=0; j < A.length; 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
        
        
        
 
        
        
        /**
               * quickSort uses the quick sort algoithm to sort an array of integers
               *
               * @author https://www.programcreek.com/2012/11/quicksort-array-in-java/
               * @version 1.0 March 22, 2021
               *
               * @param A is an array of integers to be sorted
               *
               * @return A of integers sorted in ascending order
        */         
        public static void quickSort(int[] arr, int start, int end)
        { //quick
 
            int partition = partition(arr, start, end);
 
            if(partition-1>start) {
                quickSort(arr, start, partition - 1);
            }
            if(partition+1<end) {
                quickSort(arr, partition + 1, end);
            }
        } //quick
        
        //partition is a helper method to quickSort
        public static int partition(int[] arr, int start, int end)
        { //part
            int pivot = arr[end];
 
            for(int i=start; i<end; i++){
                if(arr[i]<pivot){
                    int temp= arr[start];
                    arr[start]=arr[i];
                    arr[i]=temp;
                    start++;
                }
            }
 
            int temp = arr[start];
            arr[start] = pivot;
            arr[end] = temp;
 
            return start;
        }//part
        

 
        
        /**
               * quickSort uses the quick sort algoithm to sort an array of Strings
               *
               * @author https://www.programcreek.com/2012/11/quicksort-array-in-java/
               * @version 1.0 March 22, 2021
               *
               * @param A is an array of strings to be sorted
               *
               * @return A of strings sorted in ascending order
        */         
        public static void quickSort(String[] arr, int start, int end)
        { //quick
 
            int partition = partition(arr, start, end);
 
            if(partition-1>start) {
                quickSort(arr, start, partition - 1);
            }
            if(partition+1<end) {
                quickSort(arr, partition + 1, end);
            }
        } //quick
        
        //partition is a helper method to quickSort
        public static int partition(String[] arr, int start, int end)
        { //part
            String pivot = arr[end];
 
            for(int i=start; i<end; i++){
                if(arr[i].compareTo(pivot) < 0){
                    String temp= arr[start];
                    arr[start]=arr[i];
                    arr[i]=temp;
                    start++;
                }
            }
 
            String temp = arr[start];
            arr[start] = pivot;
            arr[end] = temp;
 
            return start;
        }//part
        

}