I really really really need help with the following question. Can you provide th
ID: 3830483 • Letter: I
Question
I really really really need help with the following question. Can you provide the CODE and OUTPUT using JAVA LANGUAGE, please?
Write an interactive program that implements a Quicksort, a Heapsort, Bubble Sort, Selection Sort, Insertion Sort, and a Mergesort. The user is prompted by your program to enter a list of 25 integers. Your program then asks the user for the sort type he/she prefers. The user is given the 6 choices. After the choice has been made, your program sorts the data by all six sorting techniques, regardless of the user's preference. Your program then outputs the list using the user's choice with the corresponding execution time (the time it took to do the sort) and also outputs the times taken for sorting the list by the other five selection recommending the fastest sorting technique (by times) for his/her input list.
Explanation / Answer
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Sortings {
private int array[];
private int length;
private static int N;
public void quickSort(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
return;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
}
static void bubbleSort(int[] arr) {
int n = arr.length;
int temp = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < (n - i); j++) {
if (arr[j - 1] > arr[j]) {
// swap elements
temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
}
public static void mergeSort(int[] a, int low, int high) {
int N = high - low;
if (N <= 1)
return;
int mid = low + N / 2;
// recursively sort
mergeSort(a, low, mid);
mergeSort(a, mid, high);
// merge two sorted subarrays
int[] temp = new int[N];
int i = low, j = mid;
for (int k = 0; k < N; k++) {
if (i == mid)
temp[k] = a[j++];
else if (j == high)
temp[k] = a[i++];
else if (a[j] < a[i])
temp[k] = a[j++];
else
temp[k] = a[i++];
}
for (int k = 0; k < N; k++)
a[low + k] = temp[k];
}
public static void insertionSort(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j - 1;
while ((i > -1) && (array[i] > key)) {
array[i + 1] = array[i];
i--;
}
array[i + 1] = key;
}
}
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int index = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[index]) {
index = j;// searching for lowest index
}
}
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
}
private void quickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number, I am taking pivot as middle index number
int pivot = array[lowerIndex + (higherIndex - lowerIndex) / 2];
// Divide into two arrays
while (i <= j) {
/**
* In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a
* number from right side which is less then the pivot value. Once
* the search is done, then we exchange both numbers.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
// move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
}
private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/* Sort Function */
public static void heapSort(int arr[]) {
heapify(arr);
for (int i = N; i > 0; i--) {
swap(arr, 0, i);
N = N - 1;
maxheap(arr, 0);
}
}
/* Function to build a heap */
public static void heapify(int arr[]) {
N = arr.length - 1;
for (int i = N / 2; i >= 0; i--)
maxheap(arr, i);
}
/* Function to swap largest element in heap */
public static void maxheap(int arr[], int i) {
int left = 2 * i;
int right = 2 * i + 1;
int max = i;
if (left <= N && arr[left] > arr[i])
max = left;
if (right <= N && arr[right] > arr[max])
max = right;
if (max != i) {
swap(arr, i, max);
maxheap(arr, max);
}
}
/* Function to swap two numbers in an array */
public static void swap(int arr[], int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String a[]) {
int[] input = new int[10];
System.out.println("Enter the value in array: ");
Scanner scan = new Scanner(System.in);
for (int i = 0; i < 10; i++) {
input[i] = scan.nextInt();
}
System.out
.println("Enter the Choice of sorting: 1. Quicksort 2. Heapsort 3. Bubble Sort 4. Selection Sort 5. Insertion Sort 6. Mergesort");
int ch = scan.nextInt();
Sortings sorter = new Sortings();
List l = new ArrayList();
long s = System.currentTimeMillis();
sorter.quickSort(input);
long e = System.currentTimeMillis();
l.add(new Time(1, e - s));
s = System.currentTimeMillis();
heapSort(input);
e = System.currentTimeMillis();
l.add(new Time(2, e - s));
s = System.currentTimeMillis();
bubbleSort(input);
e = System.currentTimeMillis();
l.add(new Time(3, e - s));
s = System.currentTimeMillis();
selectionSort(input);
e = System.currentTimeMillis();
l.add(new Time(4, e - s));
s = System.currentTimeMillis();
insertionSort(input);
e = System.currentTimeMillis();
l.add(new Time(5, e - s));
s = System.currentTimeMillis();
mergeSort(input, 0, input.length);
e = System.currentTimeMillis();
l.add(new Time(6, e - s));
Collections.sort(l);
System.out.println("Time taken by all sortings ");
System.out.println(l);
System.out.println("Time taken by Fastest sorting: " + l.get(0));
}
}
class Time implements Comparable {
int sortingType;
Long time;
public Time(int sortingType, Long time) {
super();
this.sortingType = sortingType;
this.time = time;
}
@Override
public String toString() {
return "Time [sortingType=" + sortingType + ", time=" + time + "]";
}
@Override
public int compareTo(Object o) {
return this.time.compareTo(((Time) o).time);
}
}