import java.io.*;
import java.util.*;
public class Main
{
   private static int parent(int n) {return(n-1)/2;}
   private static int leftChild(int n) {return(2*n)+1;}
   private static int rightChild(int n) {return(2*n)+2;}
   static int comparisons;
   public static void main(String[] args)
   {
       int selectionArray[] = new int[100];
       createArray(selectionArray);
       System.out.println("Array Unsorted(Selection Sort) : ");
       printArray(selectionArray);
       selectionsort(selectionArray,1,selectionArray.length-2);
       System.out.println();
       System.out.println("Array Sorted(Selection Sort): ");
       printArray(selectionArray);
       System.out.println();

       int insertArray[] = new int[100];
       createArray(insertArray);
       System.out.println("Array Unsorted(Insert Sort): ");
       printArray(insertArray);
       insertionsort(insertArray,1,insertArray.length-2);
       System.out.println();
       System.out.println("Array Sorted(Insert Sort): ");
       printArray(insertArray);
       System.out.println();

       int mergeArray[] = new int[100];
       createArray(mergeArray);
       System.out.println("Array Unsorted(Merge Sort): ");
       printArray(mergeArray);
       mergesort(mergeArray,0,mergeArray.length-1);
       System.out.println();
       System.out.println("Array Sorted(Merge Sort): ");
       printArray(mergeArray);
       System.out.println();

       int quickArray[] = new int[100];
       createArray(quickArray);
       System.out.println("Array Unsorted(Quick Sort): ");
       printArray(quickArray);
       quicksort(quickArray,0,quickArray.length-1);
       System.out.println();
       System.out.println("Array Sorted(Quick Sort): ");
       printArray(quickArray);
       System.out.println();

       int heapArray[] = new int[100];
       createArray(heapArray);
       System.out.println("Array Unsorted(Heap Sort): ");
       printArray(heapArray);
       heapsort(heapArray,heapArray.length);
       System.out.println();
       System.out.println("Array Sorted(Heap Sort): ");
       printArray(heapArray);
       System.out.println();


       comparisonTable();
       //SelectionSort Ns
       int N = 1000;
       int compareSelect[] = new int[N];
       createArray(compareSelect);
       int compareInsert[] = new int[N];
       createArray(compareInsert);
       int compareMerge[] = new int[N];
       createArray(compareMerge);
       int compareQuick[] = new int[N];
       createArray(compareQuick);
       int compareHeap[] = new int[N];
       createArray(compareHeap);
       System.out.println("1000: "+sort(1,compareSelect,compareSelect.length-2) + "        " + sort(2,compareInsert,compareInsert.length-2) + "        " + sort(3,compareMerge,compareMerge.length-2)+ "    " + sort(4,compareQuick,compareQuick.length-1) + "         " + sort(5,compareHeap,compareHeap.length) + "     " + nlogcalc(N));



       // while(N <= 10000)
       // {
           // N = N + 1000;
           // int[] compareArray = new int[N];
           // createArray(compareArray);
           // System.out.println("1000: "+sort(1,compareArray,compareArray.length-2) + "        " + sort(2,compareArray,compareArray.length-2) + "        " + sort(3,compareArray,compareArray.length-2)+ "    " + sort(4,compareArray,compareArray.length-1) + "         " + sort(5,compareArray,compareArray.length) + "     " + nlogcalc(N));
       // }

   }
   public static int[] createArray(int[] Array)
   {
       Random r = new Random();
       for(int i = 0; i < Array.length;i++)
       {
           Array[i] = r.nextInt(100);
       }
       return Array;
   }
   private static void printArray(int[] arr)
   {
       for(int i = 0; i < arr.length;i++)
       {
           if(i>0)
           {
               System.out.print(", ");
           }
           System.out.print(arr[i]);
       }
   }
   public static int selectionsort(int[ ] data, int first, int n)
   {
      comparisons = 0;
      int i, j; // Loop control variables
      int min;
      int mindex;// Index of largest value in data[first]...data[first+i]
      int temp; // Used during the swapping of two array values
      for (i = 0; i < data.length; i++)
      {
         // Calculate big as the index of the largest value in data[first]...data[first+i]:
         min = data[i];
         mindex = i;
         for(j=i;j<data.length;j++)
         {
             if(data[j] < min)
             {
                 min = data[j];
                 mindex = j;
             }
             comparisons++;
         }
         if(min < data[i])
         {
             temp = data[i];
             data[i] = data[mindex];
             data[mindex] = temp;
         }
      }
      return comparisons;
   }
   public static int insertionsort(int[ ] data, int first, int n)
   {
      comparisons = 0;
      int i, j,key,temp;// Loop control variables
      for(i=1;i<data.length;i++)//outer loop start @1 b/c it has no left(sorted)
      {
          key = data[i];
          j = i-1;
          while(j >=0 && key < data[j])
          {
              temp = data[j];
              data[j] = data[j+1];
              data[j+1] = temp;
              j--;
              comparisons++;
          }
      }
      return comparisons;
   }
   public static int mergesort (int[] list, int low, int high)
   {
       int comparisons = 0;
       if (low == high)
        return 0;
       else {
        int mid = (low + high) / 2;
        mergesort(list, low, mid);
        mergesort(list, mid + 1, high);
        comparisons = comparisons + merge(list, low, mid, high);
       }
       return comparisons;
   }
   public static int merge(int[] data, int low, int mid, int high)
   {
       int[] Left = new int[mid - low + 2];
       for (int i = low; i <= mid; i++)
       {
            Left[i - low] = data[i];
            // populates Left
       }
       Left[mid - low + 1] = Integer.MAX_VALUE;
       int[] Right = new int[high - mid + 1];

       for (int i = mid + 1; i <= high; i++)
       {
           Right[i - mid - 1] = data[i];
           // populates right
       }
       Right[high - mid] = Integer.MAX_VALUE;
       int i = 0, j = 0;
       for (int k = low; k <= high; k++)
       {
            if (Left[i] <= Right[j])
            {
                data[k] = Left[i];
                i++;
                comparisons++;
            }
            else {
                data[k] = Right[j];
                j++;
                comparisons++;
            }
        }
       return comparisons;
   }
   private static int quicksort(int[] A, int low, int high)
   {
       comparisons = 0;
       if (low < high+1)
       {
           int p = partition(A, low, high);
           quicksort(A, low, p-1);
           quicksort(A, p+1, high);
       }
       return comparisons;
   }
   private static int partition(int[] A, int low, int high)
   {
       swap(A, low, getPivot(low, high));
       int limit = low + 1;
       for (int i = limit; i <= high; i++)
       {
           if (A[i] < A[low])
           {
               swap(A, i, limit++);
               comparisons++;
           }
       }
       swap(A, low, limit-1);
       return (limit-1);
   }
   private static int getPivot(int low, int high)
   {
    Random rand = new Random();
    return rand.nextInt((high - low) + 1) + low;
   }
   private static void swap(int[] A, int index1, int index2)
   {
     int temp = A[index1];
     A[index1] = A[index2];
     A[index2] = temp;
   }
   public static int heapsort(int[ ] data, int n)
   {
      int unsorted; // Size of the unsorted part of the array
      int temp;     // Used during the swapping of two array locations
      comparisons=0;
      makeHeap(data, n);

      unsorted = n;

      while (unsorted > 1)
      {
         unsorted--;

         // Swap the largest element (data[0]) with the final element of unsorted part
         temp = data[0];
         data[0] = data[unsorted];
         data[unsorted] = temp;
         comparisons++;

         reheapifyDown(data, unsorted);
      }
      comparisons++;
      return comparisons;
   }
   private static void makeHeap(int[ ] data, int n)
   // Precondition: data is an array with at least n elements.
   // Postcondition: The elements of data have been rearranged so that the
   // complete binary tree represented by this array is a heap.
   {
       for(int i = 1; i < n; i++)
       {
           int k = i;
           while(data[k] != data[0] && data[k] > data[parent(k)])
           {
               int temp = data[k];
               data[k] = data[(k-1)/2];
               data[(k-1)/2] = temp;
               k = (k-1)/2;
           }
       }
   }
   private static void reheapifyDown(int[ ] data, int n)
   // Precondition: n > 0, and data is an array with at least n elements. These
   // elements form a heap, except that data[0] may be in an incorrect
   // location.
   // Postcondition: The data values have been rearranged so that the first
   // n elements of data now form a heap.
   {
       int current = 0;
       int bigChild;
       boolean heapOK=false;
       while((!heapOK) && leftChild(current)<n)
       {
           if(rightChild(current)>=n)
                bigChild = leftChild(current);
           else if (data[leftChild(current)] > data[rightChild(current)])
                    bigChild=leftChild(current);
           else
                    bigChild = rightChild(current);
           if(data[current]<data[bigChild])
           {
               int temp = data[current];
               data[current] = data[bigChild];
               data[bigChild] = temp;
               current = bigChild;
               comparisons++;
           }else{
               heapOK = true;
            }
       }
   }
   private static void comparisonTable()
   {
       System.out.println("---------------------------------------------------------------------");
       System.out.println(" N    selectionsort insertionsort mergesort quicksort heapsort NlogN");
       System.out.println("---------------------------------------------------------------------");
   }
   public static int sort(int i,int[] data,int n)
   {
       int compareNum = 0;
       switch(i)
       {
           case 1:
                compareNum = selectionsort(data,0,n);
                break;
           case 2:
                compareNum = insertionsort(data,0,n);
                break;
           case 3:
                compareNum = mergesort(data,0,n);
                break;
           case 4:
                compareNum = quicksort(data,0,n);
                break;
           case 5:
                compareNum = heapsort(data,n);
                break;
       }
       return compareNum;
   }
   public static int nlogcalc(int n)
   {
       n = n * log(n,2);
       return n;
   }
   public static int log(int x,int base)
   {
       return (int)(Math.log(x)/Math.log(base));
   }
}