Question

Write a program in Java to sort the given array using merge sort, quick sort, insertion sort, selection sort and bubble sort based on the input from the user which sorting technique they wanted to use. Get the array size, array elements from the user, and also display the sorted array along with the name of the sorting technique used.

Answer 1

Hi,

Please find the below code according to the problem statement.

-----------------------------------------------------------------------------------------

ArraySort.java

-----------------------------------------------------------------------------------------

import java.util.Arrays;
import java.util.Scanner;

public class ArraySort {

   public static void main(String[] args) {

       Scanner sc = new Scanner(System.in);
       System.out.print("Please enter the array size : ");
       int size = sc.nextInt();
       System.out.println("\nPlease enter " + size + " elements : ");
       int[] arr = new int[size];
       for (int i = 0; i < size; i++)
           arr[i] = sc.nextInt();
       boolean flag = false;
       while (!flag) {
           System.out.println("Please choose one of the Below sorting techniques :");
           System.out.println("A. Merge Sort\n" + "B. Quick Sort\n" + "C. Insertion Sort\n" + "D. Selection Sort\n"
                   + "E. Bubble Sort");
           char input = sc.next().toLowerCase().charAt(0);
           switch (input) {
           case 'a':
               mergeSort(arr, 0, arr.length - 1);
               System.out.println("Merge Sort is used, Elements of array after sort are : " + Arrays.toString(arr));
               flag = true;
               break;
           case 'b':
               quickSort(arr, 0, arr.length - 1);
               System.out.println("Quick Sort is used, Elements of array after sort are : " + Arrays.toString(arr));
               flag = true;
               break;
           case 'c':
               insertionSort(arr);
               System.out
                       .println("Insertion Sort is used, Elements of array after sort are : " + Arrays.toString(arr));
               flag = true;
               break;
           case 'd':
               selectionSort(arr);
               System.out
                       .println("Selection Sort is used, Elements of array after sort are : " + Arrays.toString(arr));
               flag = true;
               break;
           case 'e':
               bubbleSort(arr);
               System.out.println("Bubble Sort is used, Elements of array after sort are : " + Arrays.toString(arr));
               flag = true;
               break;
           default:
               System.out.println("Invalid Input!! Please try again");
           }
       } sc.close();
   }

   public static void mergeSort(int[] array, int left, int right) {
       if (right <= left)
           return;
       int mid = (left + right) / 2;
       mergeSort(array, left, mid);
       mergeSort(array, mid + 1, right);
       merge(array, left, mid, right);
   }

   static void merge(int[] array, int left, int mid, int right) {
       // calculating lengths
       int lengthLeft = mid - left + 1;
       int lengthRight = right - mid;

       // creating temporary subarrays
       int leftArray[] = new int[lengthLeft];
       int rightArray[] = new int[lengthRight];

       // copying our sorted subarrays into temporaries
       for (int i = 0; i < lengthLeft; i++)
           leftArray[i] = array[left + i];
       for (int i = 0; i < lengthRight; i++)
           rightArray[i] = array[mid + i + 1];

       // iterators containing current index of temp subarrays
       int leftIndex = 0;
       int rightIndex = 0;

       // copying from leftArray and rightArray back into array
       for (int i = left; i < right + 1; i++) {
           // if there are still uncopied elements in R and L, copy minimum of the two
           if (leftIndex < lengthLeft && rightIndex < lengthRight) {
               if (leftArray[leftIndex] < rightArray[rightIndex]) {
                   array[i] = leftArray[leftIndex];
                   leftIndex++;
               } else {
                   array[i] = rightArray[rightIndex];
                   rightIndex++;
               }
           }
           // if all the elements have been copied from rightArray, copy the rest of
           // leftArray
           else if (leftIndex < lengthLeft) {
               array[i] = leftArray[leftIndex];
               leftIndex++;
           }
           // if all the elements have been copied from leftArray, copy the rest of
           // rightArray
           else if (rightIndex < lengthRight) {
               array[i] = rightArray[rightIndex];
               rightIndex++;
           }
       }
   }

   public static void insertionSort(int[] array) {
       for (int i = 1; i < array.length; i++) {
           int current = array[i];
           int j = i - 1;
           while (j >= 0 && current < array[j]) {
               array[j + 1] = array[j];
               j--;
           }
           // at this point we've exited, so j is either -1
           // or it's at the first element where current >= a[j]
           array[j + 1] = current;
       }
   }

   public static void selectionSort(int[] array) {
       for (int i = 0; i < array.length; i++) {
           int min = array[i];
           int minId = i;
           for (int j = i + 1; j < array.length; j++) {
               if (array[j] < min) {
                   min = array[j];
                   minId = j;
               }
           }
           // swapping
           int temp = array[i];
           array[i] = min;
           array[minId] = temp;
       }
   }

   public static void bubbleSort(int[] a) {
       boolean sorted = false;
       int temp;
       while (!sorted) {
           sorted = true;
           for (int i = 0; i < a.length - 1; i++) {
               if (a[i] > a[i + 1]) {
                   temp = a[i];
                   a[i] = a[i + 1];
                   a[i + 1] = temp;
                   sorted = false;
               }
           }
       }
   }

   static int partition(int[] array, int begin, int end) {
       int pivot = end;

       int counter = begin;
       for (int i = begin; i < end; i++) {
           if (array[i] < array[pivot]) {
               int temp = array[counter];
               array[counter] = array[i];
               array[i] = temp;
               counter++;
           }
       }
       int temp = array[pivot];
       array[pivot] = array[counter];
       array[counter] = temp;

       return counter;
   }

   public static void quickSort(int[] array, int begin, int end) {
       if (end <= begin)
           return;
       int pivot = partition(array, begin, end);
       quickSort(array, begin, pivot - 1);
       quickSort(array, pivot + 1, end);
   }
}

Sample output:

1.

2.

3.

4.

5.

I hope this helps you!!

Thanks.