Question

you will analyse two algorithms for finding the median of an array of integers. You will compare both algorithms in terms of timing, and hopefully design a hybrid algorithm that uses both, depending on input size. You will write a report describing your experiments and results.

the following Java program implements two algorithms for finding the median of an array of integers. The first uses merge sort, and the other implements the recursive linear time selection algorithm, the task is to do the following:

1. Insert some timing statements into the program to get the compute time to run the merge sort based algorithm on arrays of diferent size.
2. Perform an experiment on arrays of diferent sizes. Gather the results, and create a chart that maps size vs time. Since this algorithm is O(n lg n), you may assume the time is approximately (cn lg n). Try to estimate the hidden constant c.
3. Insert some timing statements in the recursive linear time program. Use a low threshold, as provided in the original program. Gather the results as you did for the first program and perform a similar analysis.
4. Put both of your charts on the same graph and figure out if the curves intersect, and if yes, at which size.
5. Perform another experiment, this time using arrays with a fixed large size, but varying the threshold. Create a chart of threshold vs total time. Find out the optimal threshold. Is the optimal threshold the same as the one you found by intersecting the curves?
6. Create a report that describes the results your experiments. An experiment report should provide enough details so someone reading your report could reproduce the experiment and arrive at the same conclusion.

************************************************************

public class Selection {
static int threshold = 5;
static int size = 11;
  
public static void main(String[] args) {
int[] a = new int[size];
for (int i=0;i<size;i++)
a[i]=(int)(Math.random()*1000);
int index = (int)(Math.random()*size);
System.out.println("input array");
for (int i=0;i<size;i++)
System.out.println(a[i]);   
int result = linearSelection(a,0,size-1,index);
System.out.println("result: index "+index+" value "+a[index]);
System.out.println("final array");
for (int i=0;i<size;i++)
System.out.println(a[i]);
}
public static void merge(int[]a, int p, int q, int r){
// merges subarrays a[p..q] and a[q+1..r]
int n1=q-p+1;
int n2=r-q;
int[] left = new int[n1];
int[] right = new int[n2];
for (int i=0; i<n1; i++)
left[i]=a[p+i];
for (int i=0; i<n2; i++)
right[i]=a[q+i+1];
int i=0;
int j=0;
int k=p;
while (i<n1 && j<n2)
if (left[i]<=right[j])
a[k++]=left[i++];
else
a[k++]=right[j++];
while (i<n1)
a[k++]=left[i++];
while (j<n2)
a[k++]=right[j++];
}
public static void insertionSort(int[] a, int p, int r){
// sorts subarray a[p..r]
for (int j=p+1; j<=r; j++){
int k=a[j];
int i=j-1;
while (i>=p && a[i]>k){
a[i+1]=a[i];
i--;
}
a[i+1]=k;
}
}
public static void mergeSort(int[] a, int p, int r){
// sorts subarray a[p..r]
if (p<r){
int q=(p+r)/2;
mergeSort(a,p,q);
mergeSort(a,q+1,r);
merge(a,p,q,r);
}
}
public static int selectBySorting(int[] a, int p, int r, int i){
// sorts subarray a[p..r] and returns i
mergeSort(a,p,r);
return i;
}
public static int partition(int[] a, int p, int r){
// partitions array a[p..r] using pivot in a[r]
// returns ending position of pivot
int x=a[r];
int i=p-1;
int temp; // for exchanging
for (int j=p; j<r; j++)
if (a[j]<=x){
i++;
//exchange a[i] and a[j]
temp = a[i];
a[i]=a[j];
a[j]=temp;
}
i++;
//exchange a[i] and a[r]
temp = a[i];
a[i]=a[r];
a[r]=temp;
return i;
}
public static int linearSelection(int[] a, int p, int q, int index) {
// performs selection in linear time
// sets a[index] to the value it would be if subarray a[p..q] were sorted
// returns index
int n=q-p+1;
if (n < threshold)
return selectBySorting(a,p,q,index);
else {
int ngroups = n/5;
int[] medians = new int[ngroups];
for (int i=0; i<ngroups; i++){
insertionSort(a,p+i*5,p+i*5+4);
medians[i]=a[p+i*5+2];
}
int pivot = linearSelection(medians,0,ngroups-1,ngroups/2);
int value=medians[pivot];
int k=p;
while (value!=a[k])
k++;   
//exchange to put pivot at the end
int temp=a[k];
a[k]=a[q];
a[q]=temp;
k=partition(a,p,q);
if (index==k)
return k;
if (index<k)
return linearSelection(a,p,k-1,index);
else
return linearSelection(a,k+1,q,index);
}
}
}

Answer 1

public class Selection {
static int threshold = 5;
static int size = 11;
  
public static void main(String[] args) {
int[] a = new int[size];
for (int i=0;i<size;i++)
a[i]=(int)(Math.random()*1000);
int index = (int)(Math.random()*size);
System.out.println("input array");
for (int i=0;i<size;i++)
System.out.println(a[i]);   
int result = linearSelection(a,0,size-1,index);
System.out.println("result: index "+index+" value "+a[index]);
System.out.println("final array");
for (int i=0;i<size;i++)
System.out.println(a[i]);
}
public static void merge(int[]a, int p, int q, int r){
// merges subarrays a[p..q] and a[q+1..r]
int n1=q-p+1;
int n2=r-q;
int[] left = new int[n1];
int[] right = new int[n2];
for (int i=0; i<n1; i++)
left[i]=a[p+i];
for (int i=0; i<n2; i++)
right[i]=a[q+i+1];
int i=0;
int j=0;
int k=p;
while (i<n1 && j<n2)
if (left[i]<=right[j])
a[k++]=left[i++];
else
a[k++]=right[j++];
while (i<n1)
a[k++]=left[i++];
while (j<n2)
a[k++]=right[j++];
}
public static void insertionSort(int[] a, int p, int r){
// sorts subarray a[p..r]
for (int j=p+1; j<=r; j++){
int k=a[j];
int i=j-1;
while (i>=p && a[i]>k){
a[i+1]=a[i];
i--;
}
a[i+1]=k;
}
}
public static void mergeSort(int[] a, int p, int r){
// sorts subarray a[p..r]
if (p<r){
int q=(p+r)/2;
mergeSort(a,p,q);
mergeSort(a,q+1,r);
merge(a,p,q,r);
}
}
public static int selectBySorting(int[] a, int p, int r, int i){
// sorts subarray a[p..r] and returns i
mergeSort(a,p,r);
return i;
}
public static int partition(int[] a, int p, int r){
// partitions array a[p..r] using pivot in a[r]
// returns ending position of pivot
int x=a[r];
int i=p-1;
int temp; // for exchanging
for (int j=p; j<r; j++)
if (a[j]<=x){
i++;
//exchange a[i] and a[j]
temp = a[i];
a[i]=a[j];
a[j]=temp;
}
i++;
//exchange a[i] and a[r]
temp = a[i];
a[i]=a[r];
a[r]=temp;
return i;
}

What you need to do in it or in both the algorithms just add two for loops one inside other inside your main method the loops will start from 0 run ups to 1000 for the sake of computing the time taken in execution in milliseconds an I hope you'll get what u want. It's very time consuming to write whole program so I just copied your program and tell you what to do.