// Java program for menu-driven sorting of
// an array using various sorting algorithms

// Importing required classes
import java.util.Arrays;
import java.util.Scanner;

// Main Class
public class Sorting {

   // Method to perform Bubble Sort
   public static void bubbleSort(int[] arr) {
      int n = arr.length;
      for (int i = 0; i < n - 1; i++) {
         for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
               // Swap arr[j] and arr[j+1]
               int temp = arr[j];
               arr[j] = arr[j + 1];
               arr[j + 1] = temp;
            }
         }
      }
   }

   // Method to perform Selection Sort
   public static void selectionSort(int[] arr) {
      int n = arr.length;
      for (int i = 0; i < n - 1; i++) {
         int minIndex = i;
         for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
               minIndex = j;
            }
         }

         // Swap arr[i] and arr[minIndex]
         int temp = arr[minIndex];
         arr[minIndex] = arr[i];
         arr[i] = temp;
      }
   }

   // Method to perform Insertion Sort
   public static void insertionSort(int[] arr) {
      int n = arr.length;
      for (int i = 1; i < n; ++i) {
         int key = arr[i];
         int j = i - 1;

         // Move elements of arr[0..i-1] that are greater than key
         // to one position ahead of their current position
         while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
         }
         arr[j + 1] = key;
      }
   }

   // Method to perform Merge Sort
   public static void mergeSort(int[] arr, int l, int r) {
      if (l < r) {
         int m = l + (r - l) / 2;

         // Sort first and second halves
         mergeSort(arr, l, m);
         mergeSort(arr, m + 1, r);

         // Merge the sorted halves
         merge(arr, l, m, r);
      }
   }

   public static void merge(int[] arr, int l, int m, int r) {
      int n1 = m - l + 1;
      int n2 = r - m;

      // Create temp arrays
      int[] L = new int[n1];
      int[] R = new int[n2];

      // Copy data to temp arrays
      for (int i = 0; i < n1; ++i)
         L[i] = arr[l + i];
      for (int j = 0; j < n2; ++j)
         R[j] = arr[m + 1 + j];

      // Merge the temp arrays

      // Initial indexes of first and second subarrays
      int i = 0, j = 0;

      // Initial index of merged subarray array
      int k = l;
      while (i < n1 && j < n2) {
         if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
         } else {
            arr[k] = R[j];
            j++;
         }
         k++;
      }

      // Copy remaining elements of L[] if any
      while (i < n1) {
         arr[k] = L[i];
         i++;
         k++;
      }

      // Copy remaining elements of R[] if any
      while (j < n2) {
         arr[k] = R[j];
         j++;
         k++;
      }
   }

   // Method to perform Quick Sort
   public static void quickSort(int[] arr, int low, int high) {
      if (low < high) {
         int pi = partition(arr, low, high);

         // Recursively sort elements before
         // partition and after partition
         quickSort(arr, low, pi - 1);
         quickSort(arr, pi + 1, high);
      }
   }

   public static int partition(int[] arr, int low, int high) {
      int pivot = arr[high];
      int i = (low - 1); // Index of smaller element
      for (int j = low; j < high; j++) {
         // If current element is smaller than or
         // equal to pivot
         if (arr[j] <= pivot) {
            i++;

            // Swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
         }
      }

      // Swap arr[i+1] and arr[high] (or pivot)
      int temp = arr[i + 1];
      arr[i + 1] = arr[high];
      arr[high] = temp;

      return i + 1;
   }

   // Method to perform Heap Sort
   public static void heapSort(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);
      }
   }

   public static void heapify(int[] arr, int n, int i) {
      int largest = i; // Initialize largest as root
      int left = 2 * i + 1; // left = 2*i + 1
      int right = 2 * i + 2; // right = 2*i + 2

      // If left child is larger than root
      if (left < n && arr[left] > arr[largest])
         largest = left;

      // If right child is larger than largest so far
      if (right < n && arr[right] > arr[largest])
         largest = right;

      // 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);
      }
   }

   // Main driver method
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);

      // Taking array input from the user
      System.out.println("Enter the number of elements in the array:");
      int n = sc.nextInt();
      int[] arr = new int[n];

      System.out.println("Enter the elements of the array:");
      for (int i = 0; i < n; i++) {
         arr[i] = sc.nextInt();
      }

      // Menu for sorting options
      System.out.println("Choose the sorting method:");
      System.out.println("1. Bubble Sort");
      System.out.println("2. Selection Sort");
      System.out.println("3. Insertion Sort");
      System.out.println("4. Merge Sort");
      System.out.println("5. Quick Sort");
      System.out.println("6. Heap Sort");
      int choice = sc.nextInt();

      // Sorting based on user choice
      switch (choice) {
         case 1:
            bubbleSort(arr);
            System.out.println("Array sorted using Bubble Sort:");
            break;
         case 2:
            selectionSort(arr);
            System.out.println("Array sorted using Selection Sort:");
            break;
         case 3:
            insertionSort(arr);
            System.out.println("Array sorted using Insertion Sort:");
            break;
         case 4:
            mergeSort(arr, 0, arr.length - 1);
            System.out.println("Array sorted using Merge Sort:");
            break;
         case 5:
            quickSort(arr, 0, arr.length - 1);
            System.out.println("Array sorted using Quick Sort:");
            break;
         case 6:
            heapSort(arr);
            System.out.println("Array sorted using Heap Sort:");
            break;
         default:
            System.out.println("Invalid choice! No sorting performed.");
            return;
      }

      // Printing the sorted array
      System.out.println(Arrays.toString(arr));
      sc.close();
   }
}