Algorithm Project Code.txt

package javaapplication38;

import java.util.Random;
import java.util.*;

public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
 
       long startTime = 0, stopTime = 0;
       
       
    Scanner Size = new Scanner (System.in);
    System.out.println (" Enter array size : ");
    int ArrSize = Size.nextInt ();
    
    Random rand = new Random() ;
         // Creatw array of 10 random integers between 0 to 99 //
    System.out.println (" Random array generated by Random method is : ");
    int [] numbersArray = new int[ArrSize];
    for (int i=0 ; i < numbersArray.length; i++)
     {
          numbersArray[i] = rand.nextInt(100);
          System.out.println(numbersArray[i] + " ");
     }
     
     
        boolean done=false;
        while (done==false) {
            
                   Scanner N = new Scanner (System.in);
       System.out.println("__________ ");
       System.out.println( "Array type (1) Increasing (2) Decreasing (3) Random (4) Exit " );
       int Arraytype = N.nextInt();

        switch (Arraytype) {

        
                case 1 :
                    
            Arrays.sort(numbersArray);
            System.out.println("\n Array after Increasing sort:");
            for (int i = 0; i < numbersArray.length; i++) {
            System.out.println(numbersArray[i] + " ");
            }


        
        break;
        
            case 2 :
            int temp=0;
            System.out.println("\n Array after Decreasing sort:");
            for (int i = 0; i < numbersArray.length; i++) {     
            for (int j = i+1; j < numbersArray.length; j++) {     
               if(numbersArray[i] < numbersArray[j]) {    
                   temp = numbersArray[i];    
                   numbersArray[i] = numbersArray[j];    
                   numbersArray[j] = temp;   
                    }
                
            }
                System.out.println(numbersArray[i] + " ");
            }
            
            break;
        
            case 3 :

                break;
               
            case 4 : 
                System.exit(0);
        }
    
        Scanner input = new Scanner(System.in);
        System.out.println("_____ Sort Type   _____ ");
        System.out.println("1- Insertion");
        System.out.println("2- Merge");
        System.out.println("3- Heap");
        System.out.println("4- Quick");
        System.out.println("5- Exit");
        System.out.print("Enter the number of the algorithm or 5 to exit: ");
       
       int number = input.nextInt();
        switch(number){
            case 1:{
                //InsertionstartTime = System.nanoTime();
               int clone1[] = numbersArray.clone();
               startTime = System.nanoTime();
               Insertion inerstion = new Insertion(clone1); 
               stopTime = System.nanoTime();
                long InsertionrunningTime = (stopTime - startTime );      
        
System.out.println("Insertion Sort Execution time in nanoseconds is "+InsertionrunningTime+" ns" );
               
      
               break;
                
                
            }
            case 2:{
               int clone2[] = numbersArray.clone();
               startTime = System.nanoTime();
               Merge merge = new Merge(clone2);
               stopTime = System.nanoTime();
               
        long MergerunningTime =(stopTime - startTime); //Total execution time
        
               System.out.println("Merge Sort Execution time in nanoseconds is "+MergerunningTime+" ns" );
               break;
                
            }
            case 3:{
                int clone3[] = numbersArray.clone();
                startTime = System.nanoTime();
                Heap heap = new Heap(clone3);
                stopTime = System.nanoTime();
        
        long HeaprunningTime = (stopTime - startTime); //Total execution time
        
                System.out.println("Heap Sort Execution time in nanoseconds is "+HeaprunningTime+" ns" );
               break;
                
            }
            case 4:{
                int clone4[] = numbersArray.clone();
                startTime = System.nanoTime();
                Quick quick = new Quick(clone4);
                stopTime = System.nanoTime();
        
        long QuickrunningTime = (stopTime - startTime); //Total execution time
        
                System.out.println("Quick Sort Execution time in nanoseconds is "+QuickrunningTime+" ns" );
               
               break;
                
            }
            
            
            case 5:{
              done = true;
               
                
            }
          }
       
            
     
        }
        

       
        
       
    }
    
}

class Heap{

    public Heap(int[] numbers) {
    
    // Print the unsorted array //
    System.out.println("Before Heap Sort:");
    printArray(numbers);
 
        // Function call
        sort(numbers);
 
        System.out.println("After Heap Sort");
        printArray(numbers);
        
        
    }
    
    public void sort(int arr[])
    {
        int N = arr.length;
 
        // Build heap (rearrange array)
        for (int i = N / 2 - 1; i >= 0; i--)
            heapify(arr, N, i);
 
        // One by one extract an element from heap
        for (int i = N - 1; i > 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
 
            // call max heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }
 // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    void heapify(int arr[], int N, int i)
    {
        int largest = i; // Initialize largest as root
        int l = 2 * i + 1; // left = 2*i + 1
        int r = 2 * i + 2; // right = 2*i + 2
 
        // If left child is larger than root
        if (l < N && arr[l] > arr[largest])
            largest = l;
 
        // If right child is larger than largest so far
        if (r < N && arr[r] > arr[largest])
            largest = r;
 
        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
 
            // Recursively heapify the affected sub-tree
            heapify(arr, N, largest);
        }
    }
    /* A utility function to print array of size n */
    static void printArray(int arr[])
    {
        int N = arr.length;
 
        for (int i = 0; i < N; ++i)
            System.out.println(arr[i]);
        System.out.println();
    }
    
    
    
}

class Merge{

    public Merge(int[] numbers) {
                
		
	   System.out.println("Before Merge Sort"); // array before mergeSort function 
	     for (int element: numbers) {
            System.out.println(element);
        }
	   
	   mergeSort(numbers); // merging function call 
	   
	   System.out.println("\n After Merge Sort:"); // array after mergeSort function 
	   for (int element: numbers) {
            System.out.println(element);
        }
    }
        public void mergeSort (int[] inputArray) {
        int inputLength = inputArray.length;

        if (inputLength < 2) { // array with 1 element //
         return;
        }
        int midIndex = inputLength / 2; // divide the length of array to 2 //
        int[] leftHalf = new int[midIndex]; // create a subarray (left) //
        int[] rightHalf = new int[inputLength - midIndex]; // create a subarray (right)  //
        // note; the midIndex was subtracted from inputLength for cases where size is odd (avoide leavimg an element off  //
        
        for (int i = 0; i < midIndex; i++) {
             leftHalf[i] = inputArray[i]; // copy from original to left subarray  //
        }
        
        for (int i = midIndex; i < inputLength; i++) {
            rightHalf[i - midIndex] = inputArray[i]; // copy from original to right subarray  //
        }
      
       mergeSort(leftHalf); // merge function call for left subarray //
       mergeSort(rightHalf); // merge function call for right subarray //
       merge(inputArray, leftHalf, rightHalf); // merge two sorted subarrays //
    }
        
      public void merge (int[] inputArray, int[] leftHalf, int[] rightHalf) {
        int leftSize = leftHalf.length; // get left subarray size //
        int rightSize = rightHalf.length; // get right subarray size //
        int i = 0, j = 0, k = 0; // the looping keys for each array (merged, left and right array) //
       while (i < leftSize && j < rightSize) { // loop until the last indez //
         if (leftHalf[i] <= rightHalf[j]) { //  the element in left subarray is smaller! //
         inputArray[k] = leftHalf[i];  // therfore elementt is added to merged array 
         i++; // increment for next element in keft subarray\
         }
         else {
         inputArray[k] = rightHalf[j]; // therfore elementt is added to merged array //
         j++;  // increment for next element in right subarray //
         } 
         k++;
       }
       
       while (i < leftSize) { // if there are no eleemnts in left subarray we will bypass //
        inputArray[k] = leftHalf[i];
        i++;
        k++;
        }
        
       while (j < rightSize) { // if there are no eleemnts in right subarray we will bypass //
        inputArray[k] = rightHalf[j];
        j++;
        k++;
       }
    }
   
    
}

class Insertion{

    public Insertion(int[] numbers) {
      
    
    // Print the unsorted array //
   System.out.println("Before Insertion Sort:");
   printArray(numbers);
    
    
    insertionsort(numbers); // Calling the sort function //
    // Print the sorted array //
    System.out.println("\n After Insertion Sort:'");
    printArray (numbers); 
    }
    
      public void printArray(int[] numbers) 
    {
      for (int i=0; i < numbers.length; i++)
      {
      System.out.println(numbers[i]);
      }
    }
    
    public void insertionsort (int[] inputArray)
    {
      for (int i=1 ; i < inputArray.length; i++) // Loop starts from i=1 becouse i=0 is sorted by itself //
      {
          int currentValue = inputArray[i]; // Copy the current value into temp var //
          int j = i-1; // Walk back towards the beginning of the array  //
          
          
          // The while loop will keep testing until the conditions reach 0 or a number that is less than or equal to the current value //
          while(j>=0 && inputArray[j] > currentValue ) // First condition to stop walking back once the program reach the beginning of the array , Second condition to compare value at j with the current value at i  //  
          {
          inputArray[j+1]=inputArray[j]; // Shifting //
          j--; // Decrement to keep walk back towards the beginning of the array //
          }
       inputArray[j+1]=currentValue; // Put the temp value into its correct spot // 
      }  
    }
   
    
}

class Quick{

    public Quick(int[] numbers) {

    System.out.println("Before Quick Sort:");
    printArray(numbers);

    quicksort(numbers);

    System.out.println("\n After Quick Sort:");
    printArray(numbers);
    }
    
    public void quicksort(int[] array) {
    quicksort(array, 0, array.length - 1);
  }

  public void quicksort(int[] array, int lowIndex, int highIndex) {

    if (lowIndex >= highIndex) {
      return;
    }

    int pivotIndex = new Random().nextInt(highIndex - lowIndex) + lowIndex;
    int pivot = array[pivotIndex];
    swap(array, pivotIndex, highIndex);

    int leftPointer = partition(array, lowIndex, highIndex, pivot);

    quicksort(array, lowIndex, leftPointer - 1);
    quicksort(array, leftPointer + 1, highIndex);

  }

  public int partition(int[] array, int lowIndex, int highIndex, int pivot) {
    int leftPointer = lowIndex;
    int rightPointer = highIndex - 1;

    while (leftPointer < rightPointer) {

      // Walk from the left until we find a number greater than the pivot, or hit the right pointer.
      while (array[leftPointer] <= pivot && leftPointer < rightPointer) {
        leftPointer++;
      }

      // Walk from the right until we find a number less than the pivot, or hit the left pointer.
      while (array[rightPointer] >= pivot && leftPointer < rightPointer) {
        rightPointer--;
      }

      swap(array, leftPointer, rightPointer);
    }
    
    // This is different from what the video has, and fixes an issue where the last value could potentially be out of order. 
    // Thanks to viewer Wilson Barbosa for suggesting the fix!
    if(array[leftPointer] > array[highIndex]) {
      swap(array, leftPointer, highIndex);
    }
    else {
      leftPointer = highIndex;
    }
    
    return leftPointer;
  }

  public void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
  }

  public void printArray(int[] numbers) {
    for (int i = 0; i < numbers.length; i++) {
      System.out.println(numbers[i]);
}
} 
}