Question

Write an application that prompt user to choose Sorting Algorithm (Insertion, Merge, or Heap) in
GUI input message, then prompt user to enter numbers in GUI input message also, sort these numbers in
descending order using Selected sorting algorithm, and show the result in message dialog as shown in the
following figure.
The program contains two classes:
1- “Sort” Class which contains 3 methods named as follow:
a. InsertionSort(int[] numbers), returns sorted numbers from the passed
array using Insertion sort algorithm.
b. MergeSort(int[] numbers), returns sorted numbers from the passed
array using Merge sort algorithm.
c. HeapSort(int[] numbers), returns sorted numbers from the passed
array using Heap sort algorithm.

Answer 1

Program:

import java.util.*;

class Sort
{
   void insertionSort(int arr[], int n)
   {
       // One by one move boundary of unsorted subarray
       for (int i = 0; i < n-1; i++)
       {
           // Find the maximum element in unsorted array
           int max_ind = i;
           for (int j = i+1; j < n; j++)
               if (arr[j] > arr[max_ind])
                   max_ind = j;

           // Swap the found maximum element with the first element
           int temp = arr[max_ind];
           arr[max_ind] = arr[i];
           arr[i] = temp;
       }
   }
  
static void heapify(int arr[], int n, int i)
   {
       int smallest = i; // Initialize smalles as root
       int l = 2 * i + 1; // left = 2*i + 1
       int r = 2 * i + 2; // right = 2*i + 2

       // If left child is smaller than root
       if (l < n && arr[l] < arr[smallest])
           smallest = l;

       // If right child is smaller than smallest so far
       if (r < n && arr[r] < arr[smallest])
           smallest = r;

       // If smallest is not root
       if (smallest != i) {
           int temp = arr[i];
           arr[i] = arr[smallest];
           arr[smallest] = temp;

           // Recursively heapify the affected sub-tree
           heapify(arr, n, smallest);
       }
   }
   // main function to do heap sort
   static void heapSort(int arr[], int n)
   {
       // 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);
       }
   }
  
   void merge(int arr[], int l, int m, int r)
   {
       // Find sizes of two subarrays to be merged
       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 subarry 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++;
       }
   }

   // Main function that sorts arr[l..r] using mergeSort()
   void mergeSort(int arr[], int l, int r)
   {
       if (l < r) {
           // Find the middle point
           int m = (l + r) / 2;

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

           // Merge the sorted halves
           merge(arr, l, m, r);
       }
   }
  
   // Prints the array
   void printArray(int arr[], int n)
   {
       for (int i=0; i<n; ++i)
           System.out.print(arr[i]+" ");
       System.out.println();
   }
}

class Main
{
// Driver code
   public static void main(String args[])
   {
       Sort ob = new Sort();
       Scanner sc = new Scanner(System.in);
      
       int n, choice;
       int arr[] =new int[20];
      
       System.out.println("Enter Size of Array:");
       n = sc.nextInt();
      
       System.out.println("Enter Elements into Array:");
       for(int i=0;i<n;i++)
       {
       arr[i] = sc.nextInt();
       }
      
       System.out.println("\n1 -> Insertion Sort \n2 -> Heap Sort\n3 -> Merge Sort");
       System.out.println("\nEnter Your Choice:");
       choice = sc.nextInt();
      
       switch(choice)
       {
       case 1:
       ob.insertionSort(arr,n);
       System.out.println("\nSorted array");
       ob.printArray(arr,n);
       break;
   case 2:
   ob.heapSort(arr,n);
   System.out.println("\nSorted array");
       ob.printArray(arr,n);
       break;
   case 3:
      ob.mergeSort(arr,0, n - 1);
System.out.println("\nSorted array");
   ob.printArray(arr,n);
break;
default:
System.out.println("Invalid Coice");
break;
       }
      
   }
}

Screenshots:

Output:

1. Insertion Sort

2. Heap Sort

3. Merge Sort