Write a Java Sorting Application with two classes, JavaSort and JavaSortTest. Yo
ID: 3794737 • Letter: W
Question
Write a Java Sorting Application with two classes, JavaSort and JavaSortTest. Your JavaSort Class, as a minimum must contain sorting methods for BubbleSort, InsertionSort, ShellSort, MergeSort, and Quicksort. Your application must generate: an array of thirteen random integers from 1-99, then prompt the user to select a sorting option (Bubble Sort, Insertion Sort, Shell Sort, Merge Sort, or Quick Sort) Your application must: Account for duplications Show each completed pass of the sort on a new line with arrays surrounded by square brackets until sortedExplanation / Answer
import java.util.HashSet;
import java.util.Scanner;
public class JavaSortTest {
static int arr[] = new int[13];
static HashSet<Integer> set;
public static void main(String[] args) {
JavaSort sort=new JavaSort();
set=new HashSet<>();
for (int i = 0; i < 13;) {
int number=(int) (Math.random()*100);
if(!set.contains(number))
{
set.add(number);
arr[i]=number;
i++;
}
}
Scanner s=new Scanner(System.in);
System.out.println("Enter 1 For Insertion Sort ");
System.out.println("Enter 2 For Bubble Sort ");
System.out.println("Enter 3 For Merge Sort ");
System.out.println("Enter 4 For Quick Sort ");
System.out.println("Enter 5 For Shell Sort ");
int choice =s.nextInt();
switch (choice) {
case 1:
JavaSort.doInsertionSort(arr);
break;
case 2:
JavaSort.bubble_srt(arr);
break;
case 3:
sort.sort(arr);;
break;
case 4:
sort.sorting(arr);
break;
case 5:
JavaSort.shellSort(arr);
break;
default:
System.out.println("Enter Proper Choice");
break;
}
//JavaSort.shellSort(arr);
//sort.sorting(arr);
//sort.sort(arr);
//JavaSort.doInsertionSort(arr);
JavaSort.bubble_srt(arr);
}
}
public class JavaSort {
private int[] array;
private int[] tempMergArr;
private int length;
//For Bubble Sort
public static void bubble_srt(int array[]) {
int n = array.length;
int k;
for (int m = n; m >= 0; m--) {
for (int i = 0; i < n - 1; i++) {
k = i + 1;
if (array[i] > array[k]) {
swapNumbers(i, k, array);
}
}
printNumbers(array);
}
}
private static void swapNumbers(int i, int j, int[] array) {
int temp;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
private static void printNumbers(int[] input) {
for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + ", ");
}
System.out.println(" ");
}
//For Insertion Sort
public static void doInsertionSort(int[] input){
int temp;
for (int i = 1; i < input.length; i++) {
for(int j = i ; j > 0 ; j--){
if(input[j] < input[j-1]){
temp = input[j];
input[j] = input[j-1];
input[j-1] = temp;
}
}
printNumbers(input);
}
//return input;
}
//For Merge Sort
public void sort(int inputArr[]) {
this.array = inputArr;
this.length = inputArr.length;
this.tempMergArr = new int[length];
doMergeSort(0, length - 1);
}
private void doMergeSort(int lowerIndex, int higherIndex) {
if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
// Below step sorts the left side of the array
doMergeSort(lowerIndex, middle);
// Below step sorts the right side of the array
doMergeSort(middle + 1, higherIndex);
// Now merge both sides
mergeParts(lowerIndex, middle, higherIndex);
printNumbers(array);
}
}
private void mergeParts(int lowerIndex, int middle, int higherIndex) {
for (int i = lowerIndex; i <= higherIndex; i++) {
tempMergArr[i] = array[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (tempMergArr[i] <= tempMergArr[j]) {
array[k] = tempMergArr[i];
i++;
} else {
array[k] = tempMergArr[j];
j++;
}
k++;
}
while (i <= middle) {
array[k] = tempMergArr[i];
k++;
i++;
}
}
//For Quick Sort
public void sorting(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
return;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
}
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--;
}
}
printNumbers(array);
// 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;
}
//For Shell Sort
public static void shellSort(int[] array) {
int inner, outer;
int temp;
int h = 1;
while (h <= array.length / 3) {
h = h * 3 + 1;
}
while (h > 0) {
for (outer = h; outer < array.length; outer++) {
temp = array[outer];
inner = outer;
while (inner > h - 1 && array[inner - h] >= temp) {
array[inner] = array[inner - h];
inner -= h;
}
array[inner] = temp;
printNumbers(array);
}
h = (h - 1) / 3;
}
}
}
Output
Enter 1 For Insertion Sort
Enter 2 For Bubble Sort
Enter 3 For Merge Sort
Enter 4 For Quick Sort
Enter 5 For Shell Sort
2
71, 97, 73, 11, 89, 87, 78, 57, 42, 13, 64, 90, 99,
71, 73, 11, 89, 87, 78, 57, 42, 13, 64, 90, 97, 99,
71, 11, 73, 87, 78, 57, 42, 13, 64, 89, 90, 97, 99,
11, 71, 73, 78, 57, 42, 13, 64, 87, 89, 90, 97, 99,
11, 71, 73, 57, 42, 13, 64, 78, 87, 89, 90, 97, 99,
11, 71, 57, 42, 13, 64, 73, 78, 87, 89, 90, 97, 99,
11, 57, 42, 13, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 42, 13, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,
11, 13, 42, 57, 64, 71, 73, 78, 87, 89, 90, 97, 99,