I really really really need help with the following question. Can you provide th
ID: 3832690 • 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.
Can you please also show the RESULTS or OUTPUT? Thank you
Explanation / Answer
Below is your code. Because of less time, I am giving outputs for two user choices only. You can run it and analyze the result.
Sorter.java
import java.util.Arrays;
import java.util.Scanner;
public class Sorter {
private static int N;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Please enter 25 integers for your array.");
int[] arr = new int[25];
int[] arr1 = new int[25];
int[] arr2 = new int[25];
int[] arr3 = new int[25];
int[] arr4 = new int[25];
int[] arr5 = new int[25];
int[] arr6 = new int[25];
int count = 0;
while (count < 25) {
arr[count++] = Integer.parseInt(sc.nextLine());
}
arr1 = Arrays.copyOf(arr, arr.length);// copying data of array to 6
// arrays used in sorting
arr2 = Arrays.copyOf(arr, arr.length);
arr3 = Arrays.copyOf(arr, arr.length);
arr4 = Arrays.copyOf(arr, arr.length);
arr5 = Arrays.copyOf(arr, arr.length);
arr6 = Arrays.copyOf(arr, arr.length);
System.out.println("Please choose the sorting algorithm: ");
System.out.println("1. QuickSort");
System.out.println("2. HeapSort");
System.out.println("3. Bubble Sort");
System.out.println("4. Selection Sort");
System.out.println("5. Insertion Sort");
System.out.println("6. Merge Sort");
int choice = sc.nextInt();
sc.close();
System.out.print("Your entered array:");
for (int i = 0; i < 25; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
long[] durations = new long[7]; // array to hold the durations of all
// the sorting methods.
long startTime1 = System.nanoTime();
quickSort(arr1, 0, 24);
long endTime1 = System.nanoTime();
durations[1] = endTime1 - startTime1;
long startTime2 = System.nanoTime();
hpSort(arr2);
long endTime2 = System.nanoTime();
durations[2] = endTime2 - startTime2;
long startTime3 = System.nanoTime();
bubbleSort(arr3);
long endTime3 = System.nanoTime();
durations[3] = endTime3 - startTime3;
long startTime4 = System.nanoTime();
selectionSort(arr4);
long endTime4 = System.nanoTime();
durations[4] = endTime4 - startTime4;
long startTime5 = System.nanoTime();
inSort(arr5);
long endTime5 = System.nanoTime();
durations[5] = endTime5 - startTime5;
long startTime6 = System.nanoTime();
mergeSort(arr6, 0, 24);
long endTime6 = System.nanoTime();
durations[6] = endTime6 - startTime6;
long minDuration = durations[1];
int minSortType = 1;
// getting the fastest algorithm
for (int i = 2; i < durations.length; i++) {
if (durations[i] < minDuration) {
minDuration = durations[i];
minSortType = i;
}
}
if (choice == 1) { // choice == user selection of algorithms
System.out.print("Sorted Data:");
for (int i = 0; i < 25; i++) {
System.out.print(arr1[i] + " ");
}
System.out.println();
System.out.println("Time taken by your algorithm selection : (in nano seconds)" + durations[1]);
System.out.println("Time taken by Heap sort : (in nano seconds)" + durations[2]);
System.out.println("Time taken by Bubble sort : (in nano seconds)" + durations[3]);
System.out.println("Time taken by Selection Sort : (in nano seconds)" + durations[4]);
System.out.println("Time taken by Insertion Sort : (in nano seconds)" + durations[5]);
System.out.println("Time taken by Merge Sort : (in nano seconds)" + durations[6]);
System.out.println();
System.out.println("Based on your array input, Best sorting algorithm is :" + getBestSortType(minSortType));
} else if (choice == 2) { // choice == user selection of algorithms
System.out.print("Sorted Data:");
for (int i = 0; i < 25; i++) {
System.out.print(arr2[i] + " ");
}
System.out.println();
System.out.println("Time taken by your algorithm selection : (in nano seconds)" + durations[2]);
System.out.println("Time taken by Quick Sort : (in nano seconds)" + durations[1]);
System.out.println("Time taken by Bubble sort : (in nano seconds)" + durations[3]);
System.out.println("Time taken by Selection Sort : (in nano seconds)" + durations[4]);
System.out.println("Time taken by Insertion Sort : (in nano seconds)" + durations[5]);
System.out.println("Time taken by Merge Sort : (in nano seconds)" + durations[6]);
System.out.println();
System.out.println("Based on your array input, Best sorting algorithm is :" + getBestSortType(minSortType));
} else if (choice == 3) { // choice == user selection of algorithms
System.out.print("Sorted Data:");
for (int i = 0; i < 25; i++) {
System.out.print(arr3[i] + " ");
}
System.out.println();
System.out.println("Time taken by your algorithm selection : (in nano seconds)" + durations[3]);
System.out.println("Time taken by Heap Sort : (in nano seconds)" + durations[2]);
System.out.println("Time taken by Quick Sort : (in nano seconds)" + durations[1]);
System.out.println("Time taken by Selection Sort : (in nano seconds)" + durations[4]);
System.out.println("Time taken by Insertion Sort : (in nano seconds)" + durations[5]);
System.out.println("Time taken by Merge Sort : (in nano seconds)" + durations[6]);
System.out.println();
System.out.println("Based on your array input, Best sorting algorithm is :" + getBestSortType(minSortType));
} else if (choice == 4) { // choice == user selection of algorithms
System.out.print("Sorted Data:");
for (int i = 0; i < 25; i++) {
System.out.print(arr4[i] + " ");
}
System.out.println();
System.out.println("Time taken by your algorithm selection : (in nano seconds)" + durations[4]);
System.out.println("Time taken by Bubble Sort: (in nano seconds)" + durations[3]);
System.out.println("Time taken by Heap Sort : (in nano seconds)" + durations[2]);
System.out.println("Time taken by Quick Sort : (in nano seconds)" + durations[1]);
System.out.println("Time taken by Insertion Sort : (in nano seconds)" + durations[5]);
System.out.println("Time taken by Merge Sort : (in nano seconds)" + durations[6]);
System.out.println();
System.out.println("Based on your array input, Best sorting algorithm is :" + getBestSortType(minSortType));
} else if (choice == 5) { // choice == user selection of algorithms
System.out.print("Sorted Data:");
for (int i = 0; i < 25; i++) {
System.out.print(arr5[i] + " ");
}
System.out.println();
System.out.println("Time taken by your algorithm selection : (in nano seconds)" + durations[5]);
System.out.println("Time taken by Selection Sort : (in nano seconds)" + durations[4]);
System.out.println("Time taken by Bubble Sort: (in nano seconds)" + durations[3]);
System.out.println("Time taken by Heap Sort : (in nano seconds)" + durations[2]);
System.out.println("Time taken by Quick Sort : (in nano seconds)" + durations[1]);
System.out.println("Time taken by Merge Sort : (in nano seconds)" + durations[6]);
System.out.println();
System.out.println("Based on your array input, Best sorting algorithm is :" + getBestSortType(minSortType));
} else if (choice == 6) { // choice == user selection of algorithms
System.out.print("Sorted Data:");
for (int i = 0; i < 25; i++) {
System.out.print(arr6[i] + " ");
}
System.out.println();
System.out.println("Time taken by your algorithm selection : (in nano seconds)" + durations[6]);
System.out.println("Time taken by Selection Sort : (in nano seconds)" + durations[4]);
System.out.println("Time taken by Bubble Sort: (in nano seconds)" + durations[3]);
System.out.println("Time taken by Heap Sort : (in nano seconds)" + durations[2]);
System.out.println("Time taken by Quick Sort : (in nano seconds)" + durations[1]);
System.out.println("Time taken by Insertion Sort : (in nano seconds)" + durations[5]);
System.out.println();
System.out.println("Based on your array input, Best sorting algorithm is :" + getBestSortType(minSortType));
}
}
public static String getBestSortType(int x) {
if (x == 1) {
return "Quick Sort";
} else if (x == 2) {
return "Heap Sort";
} else if (x == 3) {
return "Bubble Sort";
} else if (x == 4) {
return "Selection Sort";
} else if (x == 5) {
return "Insertion Sort";
} else {
return "Merge Sort";
}
}
/** Quick sort function **/
public static void quickSort(int arr[], int low, int high) {
int i = low, j = high;
int temp;
int pivot = arr[(low + high) / 2];
/** partition **/
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
/** swap **/
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (low < j)
quickSort(arr, low, j);
if (i < high)
quickSort(arr, i, high);
}
// Insertion Sort
public static void inSort(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;
}
}
// Heap Sort
public static void hpSort(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;
}
// Bubble sort
// current element compared to next element if greater than swapped.
public 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;
}
}
}
}
// selection sort
// select the lowest element and fit it in the right position, swap the
// current element with next lowest.
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;
}
}
/* Merge Sort function */
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];
}
}
Sample Run: -
1. This is for worst case for insertion sort when list is reverse sorted
Please enter 25 integers for your array.
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
Please choose the sorting algorithm:
1. QuickSort
2. HeapSort
3. Bubble Sort
4. Selection Sort
5. Insertion Sort
6. Merge Sort
1
Your entered array:25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Sorted Data:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Time taken by your algorithm selection : (in nano seconds)30790
Time taken by Heap sort : (in nano seconds)75110
Time taken by Bubble sort : (in nano seconds)53650
Time taken by Selection Sort : (in nano seconds)32189
Time taken by Insertion Sort : (in nano seconds)33123
Time taken by Merge Sort : (in nano seconds)46652
Based on your array input, Best sorting algorithm is :Quick Sort
2. This is for worst case of quick sort when list is already sorted: -
Please enter 25 integers for your array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Please choose the sorting algorithm:
1. QuickSort
2. HeapSort
3. Bubble Sort
4. Selection Sort
5. Insertion Sort
6. Merge Sort
5
Your entered array:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Sorted Data:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Time taken by your algorithm selection : (in nano seconds)2799
Time taken by Selection Sort : (in nano seconds)9331
Time taken by Bubble Sort: (in nano seconds)9331
Time taken by Heap Sort : (in nano seconds)32189
Time taken by Quick Sort : (in nano seconds)10263
Time taken by Merge Sort : (in nano seconds)17728
Based on your array input, Best sorting algorithm is :Insertion Sort