Use JAVA and please include the output. Implement Java versions of the insertion
ID: 3884368 • Letter: U
Question
Use JAVA and please include the output.
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
Hey, please find the code below, if you have any doubts feel free to comment.
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Project2
{
static void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
int L[] = new int [n1];
int R[] = new int [n2];
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
public static void msort(int[] a,int l, int r)
{
if (l < r)
{
int m = (l+r)/2;
msort(a, l, m);
msort(a , m+1, r);
merge(a, l, m, r);
}
}
public static void insertionSort(int[] a)
{
int n = a.length;
for (int i=1; i<n; ++i)
{
int key = a[i];
int j = i-1;
while (j>=0 && a[j] > key)
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = key;
}
}
public static void mergeSort(int[] a)
{
int l=0;
int r=a.length-1;
msort(a,l,r);
}
public static boolean gettime(int n)
{
int arr[] = new int[n];
int brr[] = new int[n];
for(int i=0;i<n;i++)
{
arr[i]= 1 + (int)(Math.random() * 10000);
brr[i]=arr[i];
}
long startTime = System.currentTimeMillis();
insertionSort(arr);
long endTime = System.currentTimeMillis();
long totalTime1 = endTime - startTime;
// System.out.println("Time taken by insertion sort"+totalTime);
startTime = System.currentTimeMillis();
mergeSort(brr);
endTime = System.currentTimeMillis();
long totalTime2 = endTime - startTime;
// System.out.println("Time taken by merge sort"+totalTime);
if(totalTime2<totalTime1)
{
return true;
}
return false;
}
public static void main (String[] args) throws java.lang.Exception
{
int ans=0;
// your code goes here
for(int i=1;i<100000;i++)
{
if(gettime(i))
{
ans=i;
break;
}
}
ans--;
System.out.println("largest input size n for which the insertion sort outperforms the merge sort on average:"+ ans);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.