JAVA Implement Java versions of the insertion sort and merge sort algorithms. Us
ID: 3883268 • Letter: J
Question
JAVA
Implement Java versions of the insertion sort and merge sort algorithms. Use the exact class and method specifications given below and use the default package. You may define additional methods in the class.
public class Project2
{
public static void insertionSort(int[] a)
public static void mergeSort(int[] a)
}
Use 0-based indexing for the arrays specified in the Java class. You may use Integer.MAX_VALUE to represent . Design a procedure to test the average running time of the two sorting algorithms based on your implementation. Determine the largest input size n for which the insertion sort outperforms the merge sort on average.
Explanation / Answer
public class Project2
{
private int[] array;
private int[] tempArray;
private int length;
public static int[] 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;
}
}
}
return input;
}
//sort the data
public void sort(int inputArray[]) {
this.array = inputArray;
this.length = inputArray.length;
this.tempArray = 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);
}
}
private void mergeParts(int lowerIndex, int middle, int higherIndex) {
for (int i = lowerIndex; i <= higherIndex; i++) {
tempArray[i] = array[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (tempArray[i] <= tempArray[j]) {
array[k] = tempArray[i];
i++;
} else {
array[k] = tempArray[j];
j++;
}
k++;
}
while (i <= middle) {
array[k] = tempArray[i];
k++;
i++;
}
public static void insertionSort(int[] a){
int[] arr1 = {51,45,85,12,45,78};
int[] arrSort = doInsertionSort(arr1);
for(int i:arrSort ){
System.out.print(i);
System.out.print(", ");
}
}
public static void mergeSort(int[] a) {
int[] inputArray = {25,45,78,95,35,24,65,87};
MyMergeSort merms = new MyMergeSort();
merms.sort(inputArray);
for(int i:inputArray){
System.out.print(i);//value printing
System.out.print(" ");
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.