package sortingalgs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List; 
/**
 * Data is output to the console with a comma this can be used inside excel to easily copy data aka excel function TEXT TO COLOUNMS  
 * I found the above method much faster than trying to create an excel sheet in netbeans  
 * @author tyler
 * @param <T>
 */
public class SortingAlgs{
    
    static int numComps = 0;
    static int numSwaps = 0;
    
    public static <T extends Comparable<T>> void mergeSort(List<T> list){
        if(list.size() < 2){
            return; 
        }
        int midway = list.size()/2; 
        List<T> left = new ArrayList<>();
        List<T> right = new ArrayList<>(); 
        for (int i = 0; i < midway; i++) {
            left.add(list.get(i));
        }
        for (int i = midway; i < list.size(); i++) {
            right.add(list.get(i)); 
        }
        mergeSort(left);
        mergeSort(right); 
        merge(left, right, list); 
        }
        
        
        
    
    public static <T extends Comparable <T>> void merge(List<T> list1, List<T> list2, List<T> ogList){
       int elements1 = list1.size(); 
       int elements2 = list2.size(); 
       int x = 0;
       int y = 0; 
       int z = 0; 
       while( x < elements1 && y < elements2){
           numComps++; 
           if(list1.get(x).compareTo(list2.get(y)) < 0 || list1.get(x).compareTo(list2.get(y)) == 0 ){
               ogList.remove(ogList.get(z));
               ogList.add(z,list1.get(x)); 
               numSwaps++;
               z++; 
               x++; 
           } else{
              ogList.remove(ogList.get(z)); 
              ogList.add(z, list2.get(y));
              numSwaps++; 
              z++;
              y++;
           }
       }
       while(x < elements1){
               ogList.remove(ogList.get(z));
               ogList.add(z,list1.get(x));
               numSwaps++;
               z++; 
               x++; 
           
       }
       while(y < elements2){
            ogList.remove(ogList.get(z)); 
              ogList.add(z, list2.get(y));
              numSwaps++; 
              z++;
              y++;
       }
           
    }
    
    
    
    
    
 //CITATION THIS METHOD WAS DEVELOPED WITH HEAVY INFLUENCE FROM THE CLASS POWERPOINT SLIDE PSUEDO CODE ALGORITHIM    
    public static <T extends Comparable<T>> void insertionSort(T[] arr){
        for(int i = 1; i < arr.length; i++){
            int nextPos = i; 
            T nextVal = arr[i];
            numComps++; 
            while(nextPos > 0 && arr[nextPos-1].compareTo(nextVal) > 0 ){
                numComps++;
                arr[nextPos] = arr[nextPos-1]; 
                numSwaps++;
                nextPos--; 
            }
            arr[nextPos] = nextVal;
            numSwaps++; 
        }   
    }
    
    //METHOD CITATION FROM ONLINE OPEN SOURCE https://www.programcreek.com/2012/11/quicksort-array-in-java/
    //method adapted to use the first term as the pivot and up and down variables from Flipped Class Lectures 
	public static void quickSort(int[] arr, int low, int high) {
        int pivot = arr[low];
        if (arr == null || arr.length == 0 || low >= high){
			return;
        }
        int up = low; 
        int down = high; 
        while(up <= down){
                numComps++; 
            while(arr[up] < pivot){
                numComps++;
                up++;
            }
                numComps++; 
            while(arr[down] > pivot){
                numComps++;
                down--; 
            }
              
            if(up <= down){
                int temporary = arr[up];
                arr[up] = arr[down]; 
                arr[down] = temporary; 
                numSwaps++; 
                up++;
                down--; 
            }
        }
        if(low < down){
            quickSort(arr,low,down); 
        } if (high > up){
            quickSort(arr,up,high); 
        }

        }
    

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
    //insertion sort test 
        Integer[] array = new Integer[10]; 
        for (int i = 0; i < 10; i++) {
            if(i % 2 == 0){
               array[i] = i * 2 ;  
            } else {
                array[i] = i; 
            }   
        }
        
        System.out.println(Arrays.toString(array));
        insertionSort(array); 
        System.out.println(Arrays.toString(array));
        
        
        System.out.println("");
        
        //quickSort test
           int[] newArray = new int[10]; 
        for (int i = 1; i < 10; i++) {
            if(i % 2 == 0){
               newArray[i] = i * 2 ;  
            } else {
                newArray[i] = i; 
            }   
        }
        
        System.out.println(Arrays.toString(newArray));
        quickSort(newArray, 0, newArray.length-1); 
        System.out.println(Arrays.toString(newArray));
        
        
        System.out.println("");
        
        
          List<Integer> newA = new ArrayList<>(); 
        for (int i = 0; i < 10; i++) {
            if(i % 2 == 0){
               Integer t = i * 2 ; 
               newA.add(t);
            } else {
                Integer w = i;
                newA.add(w); 
            }   
        }
        
        System.out.println(newA.toString());
        mergeSort(newA); 
        System.out.println(newA.toString());
        
        System.out.println("");
        

    numComps = 0; 
    numSwaps = 0;
         
    for(int n = 2; n <=  2048;){
        insertionSortTest(n);
        n*=2; 
    }
    numComps = 0; 
    numSwaps = 0;
   

    for(int n = 2; n <=  2048;){
        mergeSortTest(n);
        n*=2; 
    }  
    numComps = 0; 
    numSwaps = 0;

     for(int n = 2; n <=  2048;){
        quickSortTest(n);
        n*=2; 
    } 
     
      
    }
    public static void insertionSortTest(int n){
      Integer[] array = new Integer[n]; 
        for (int i = 0; i < n; i++) {
            if(i % 2 == 0){
               array[i] = i * 2 ;  
            } else {
                array[i] = i; 
            }   
        }
        long startTime = System.nanoTime();
        insertionSort(array); 
        long estimatedTime = System.nanoTime() - startTime;
        System.out.println("Insertion" + " , "  + n + " , " + estimatedTime + " , " + numSwaps + " , " + numComps );
        
    }
    
      public static void mergeSortTest(int n){
      List<Integer> newList = new ArrayList<>();  
        for (int i = 0; i < n; i++) {
            if(i % 2 == 0){
               newList.add(i * 2);  
            } else {
                newList.add(i); 
            }   
        }
        long startTime = System.nanoTime();
        mergeSort(newList); 
        long estimatedTime = System.nanoTime() - startTime;
        System.out.println( "Merge" + " , "  +  n + " , " + estimatedTime + " , " + numSwaps + " , " + numComps );
        
    }
     public static void quickSortTest(int n){
       int[] array = new int[n]; 
        for (int i = 0; i < n; i++) {
            if(i % 2 == 0){
               array[i] = i * 2 ;  
            } else {
                array[i] = i; 
            }   
        }
        long startTime = System.nanoTime();
        quickSort(array,0,n-1); 
        long estimatedTime = System.nanoTime() - startTime;
        System.out.println("Quick" + " , "  + n + " , " + estimatedTime + " , " + numSwaps + " , " + numComps );
       
    }
    
    


}