/******************************************************************************
 * Sorting incoming words on command line 
 * Using: 1) standard Java array sort
 *        2) selection sort
 *        3) bubble sort 
 *        4) quicksort (recursive)
 *
 * Below you can make  PRINT=true  to see intermediate results of the sorts
 * You can use these values to test:  4 7 8 3 2 9 6 0 1 5
 ******************************************************************************/
import java.util.Arrays;

public class zSort2
{
    static boolean PRINT=false;                                    //print intermediate results?

    public static void main (String[] args) 
    {
        if (args.length < 3) {
            System.out.println("Re-execute with at least 3 words");
            System.exit(-1);
        }
    
        System.out.println("Before the sort:");

        String str = "";

        for (int i=0; i < args.length; i++)
        { 
            System.out.println(args[i]);          //print each word on a separate line
            str += args[i] + " ";                 //sting out the array
        }
        System.out.println(str);

        String[] words1 = Arrays.copyOf(args, args.length);     //copy array to test multiple sorts 
        String[] words2 = Arrays.copyOf(args, args.length);     
        String[] words3 = Arrays.copyOf(args, args.length);      
        String[] words4 = Arrays.copyOf(args, args.length);     

        System.out.println();
 
        //Standard Java sort -----------------------------------------------------------------------------------
        System.out.println("STANDARD JAVA SORT============================");
        long start1 = System.nanoTime();
        Arrays.sort(words1);                             //Java standard sort
        long end1   = System.nanoTime();
        System.out.printf("\n Standard Sort duration:  %6.3f microseconds \n\n" , (end1-start1)/1000.0);

        //Selection Sort ---------------------------------------------------------------------------------------
        System.out.println("SELECTION SORT================================");
        long start2 = System.nanoTime();
        selectionSort(words2);                          //selection sort 
        long end2   = System.nanoTime();
        System.out.printf("\n Selection Sort duration: %6.3f microseconds \n\n" , (end2-start2)/1000.0);

        //Bubble sort ------------------------------------------------------------------------------------------
        System.out.println("BUBBLE SORT===================================");
        long start3 = System.nanoTime();
        bubbleSort(words3);                            //bubble sort 
        long end3   = System.nanoTime();
        System.out.printf("\n Bubble Sort duration:   %6.3f microseconds \n\n" , (end3-start3)/1000.0);

        //Recursive quick sort ---------------------------------------------------------------------------------
        System.out.println("RECURSIVE QUICKSORT===========================");
        long start4 = System.nanoTime();
        quickSort(words4);                             //recursive quicksort
        long end4   = System.nanoTime();
        System.out.printf("\n Quick Sort duration:    %6.3f microseconds \n\n" , (end4-start4)/1000.0);

        //------------------------------------------------------------------------------------------------------

        System.out.println("After the sort:");

        StringBuffer sb1 = new StringBuffer();
        StringBuffer sb2 = new StringBuffer();

        for (int i=0; i < words1.length; i++) 
        { 
            sb1 = sb1.replace(0,999,words1[i]);     //copy the string into existing stringBuffer
            System.out.println(sb1);                //print after sort
            sb2.append(sb1 + " ");                  //concatenate to a single stringBuffer
        }

        System.out.println(sb2);
    }

/*************************************************************************************************
 * SELECTION SORT method:
 * OBJECTIVE: Find the smallest element in the array, switch it with first element, then repeat.
 * 1. Search through the array for the smallest element. Notate the position of that element
 * Switch that element with the first position
 * 2. Start the array search from the second element 
 * Search through the array for the smallest element. Notate the position of that element
 * Switch that element with the second position
 * 3. Repeat again starting at the third element. etc. 
 *************************************************************************************************/  
    static void selectionSort(String[ ] array)
    { 
        String temp;
        int len = array.length; 

        if (PRINT) System.out.println("Starting with array.........: "+ Arrays.toString(array));          //<PRINT> 

        for (int i=0; i < len-1; i++)                           //loop for every element
        {
            if (PRINT) System.out.println("Loop from: " + (i+1) + " to: " + len);                         //<PRINT> 

            int min_idx = i;
            for (int j=i+1; j < len; j++)                       //find the smallest element
            {
                if (array[j].compareTo(array[min_idx]) < 0)     //is element j is smaller?
                    min_idx = j;
            }
            if (PRINT) System.out.println("\t MIN ELEMENT: " + array[min_idx]);                           //<PRINT> 

            if (min_idx != i)                                   //if min_idx is not itself
            {                                                   //  (no sense swithing with yourself)
                temp           = array[min_idx];                //switch elements
                array[min_idx] = array[i];
                array[i]       = temp;

                if (PRINT) System.out.println("\t SWITCHED ELEMENTS: " + array[min_idx] +" "+array[i]);   //<PRINT> 
            }
            if (PRINT) System.out.println("End of loop: "+ Arrays.toString(array));                       //<PRINT> 
        }
    }
 
/*********************************************************************************
 * BUBBLE SORT method:
 * OBJECTIVE: Push the largest element all the way down, then repeat.
 * Starting from the top, compare each two adjacent elements
 * if order is not correct, switch the two elements, and keep moving down.
 * when done, the largest element is positioned all the way at bottom.
 * Start the comparison again, but now compare up to next to the last element.
 * when done, the second largest element is in the second to last position
 * And so forth..
 ********************************************************************************/  
    static void bubbleSort(String[ ] array)
    { 
        String  temp;
        int     upto    = array.length;
        boolean continu = true;

        if (PRINT) System.out.println("Starting with array.........: "+ Arrays.toString(array));        //<PRINT> 

        while(continu)                                              //while there is more to switch
        {
            continu = false;                                        //always turn off

            if (PRINT) System.out.println("Loop from 1 to " + upto);                                    //<PRINT> 

            for (int i=0; i < upto-1; i++)                          //loop for every element
            {
                if (PRINT) System.out.println("\t Comparing elements: " + array[i] +" "+ array[i+1]);   //<PRINT> 

                if (array[i].compareTo(array[i+1]) > 0)             //compare 2 elements, if greater        
                {
                    temp       = array[i];                          //switch elements
                    array[i]   = array[i+1];
                    array[i+1] = temp;

                    continu = true;                                 //as long as we swap, we continue processing

                    if (PRINT) System.out.println("\t SWITCHED ELEMENTS: " + array[i+1] +" "+array[i]);     //<PRINT> 
                }
            }
            upto = upto -1; 

            if (PRINT) System.out.println("End of loop: " + Arrays.toString(array));                        //<PRINT> 
        }
    }

//*********************************************************************************************************
// QUICKSORT recursive method:
// OBJECTIVE: For each pass, position the first element exactly where it is suppose to be in the array.
// Focus on the first element, Let's call it "IT". 
// Compare IT to last element of the array, switch if necessary 
// If not switched - compare IT to next to last element in the array   
// If switched     - compare IT to next to first element in the array
// Repeat above until IT is compared against every element in the array   
// In doing so, all elements that are less than IT will move to the top of the array,
// and all elements that are greater than IT will move to the bottom of the array.
// The sort will split the array at the position where IT is supposed to be. 
// The sort will recursively call the sort for the top section, and again for the bottom section.  
//*********************************************************************************************************  
    static void quickSort(String[ ] array)
    { 
        int from = 0;                       //start the sort at 0
        int to   = array.length-1;          //end the sort at array.length-1        

        if (PRINT) System.out.println("Starting with array.........: "+ Arrays.toString(array));  //<PRINT> 

        quickSort(array, from,  to);        
    }

    static void quickSort(String[ ] array, int from, int to)    //overloaded method
    { 
        if (from >= to) return;                         //end of recurssion
        
        if (PRINT) {
            System.out.print("SORTING ARRAY index "+ from +"-"+ to +": [");                     //<PRINT> 
            for (int i=from; i<=to; i++)                                                        //<PRINT>
                System.out.print(array[i] + ", ");                                              //<PRINT>
            System.out.print("] \n");                                                           //<PRINT>
        }                                                            

        String  temp;

        int top = from;                     //index of top of the array or sub-array
        int bot = to;                       //index of bottom of array  or sub-array
        int direction = -1;                 //start compare direction -> from bottom going up
                                            //i.e. first element is compared to last element, then next to last element
        while(top < bot)                        
        {
            if (PRINT) System.out.println("\t Comparing elements: " + array[top] +" "+ array[bot]);            //<PRINT> 

            if (array[top].compareTo(array[bot]) > 0)   //if top element > bottom element
            {
                temp       = array[top];                //switch elements
                array[top] = array[bot];
                array[bot] = temp;
                direction *= -1;                        //switch compare direction

                if (PRINT) System.out.print("\t SWITCHED ELEMENTS: " + array[bot] +" "+ array[top]);           //<PRINT>
                if (PRINT) System.out.print("\t new direction: " + ((direction==1) ? "up" : "down") +"\n");    //<PRINT> 
            }
            if (direction == -1)                        //if compare direction is -> from bottom going up
                bot-- ;                                 //substract 1 from bottom array index
            else
                top++ ;                                 //add 1 to top array index
        }

        if (PRINT) System.out.println("Element: " + array[top] + " is now in proper place");                  //<PRINT> 
        if (PRINT) System.out.println("End of iteration: " + Arrays.toString(array));                         //<PRINT> 

        if (from < top-1)                          
            quickSort(array, from,  top-1);             //call recursion for the top half

        if (bot+1 < to)                          
            quickSort(array, bot+1, to);                //call recursion for the bottom half
    }
}