Question

I want just the answer to the third task. to generate a report/graph.

Thanks!

1 Problem Description Instructions. You are provided the skeleton code named Sort.java. The source file is available on Canvas in a folder named HW1. Please modify the skeleton code to solve the following tasks. . Task 1 (80 pts). Implement the Insertion Sort algorithm as discussed in Lecture 1. (Hint: use the function checked sorted to check if your output is indeed sorted.) . Task 3 (20 pts). Generate a report to discuss the time performance of the two algorithms. Compare it with their theoretical time complexity as discussed in the lecture. Plots and figures are encouraged to help draw the conclusion. See Figure 1 for an example of the plot. 60 T Selection Sort Insertion Sort (avg) Merge Sort 40 + 10 0 1,000 2,000 3,000 4,000 5,000 6,000 7,000 8,000 9,000 10,000 Problem Size (number of items to be sorted) Figure 1: An example of the time performance plot

Answer 1

IF YOU HAVE ANY DOUBTS PLEASE COMMENT BELOW I WILL THERE TO HELP YOU

ANSWER:

CODE:

import static java.lang.System.arraycopy;

import java.util.*;

public class Sort2 {

public static int[] merge_sort(int[] array, int p, int r) {

// Check if low is smaller then high, if not then the array is sorted

if (p < r) {

// Get the index of the element which is in the middle

int middle = (p + r) / 2;

// Sort the left side of the array

merge_sort(array,p, middle);

// Sort the right side of the array

merge_sort(array,middle + 1, r);

// Combine them both

merge(array,p, middle, r);

}

return array;

}

public static int[] merge(int[] array, int p, int q, int r) {

// array segment arr[low:high] contains two sorted subsegments arr[low:mid]

// and arr[mid+1:high] where mid = (low + high) / 2

final int mid = (p + r) / 2;

// temporary array into which the segments arr[low:mid] and arr[mid+1:high]

// are merged. The size needed is high - low + 1

final int[] tempArr = new int[r - p + 1];

// index variables set into segments to merge and into the tempArray

int index1 = p, index2 = mid + 1, index3 = 0;

  

while (index1 <= mid && index2 <= r) {

if (array[index1] <= array[index2]) { // copy from first segment

tempArr[index3] = array[index1];

index1++;

} else { // copy from second segment

tempArr[index3] = array[index2];

index2++;

} // end if

index3++;

} // end loop

// number of values left over (not copied into tempArr yet)

// from first segment: mid - index1 + 1

// from second segment: high - index2 + 1

// Note that only one segment will have leftovers so

// one of the following arraycopy's will not do anything

arraycopy(array, index1, tempArr, index3, mid - index1 + 1);

arraycopy(array, index2, tempArr, index3, r - index2 + 1);

// copy back from tempArr to arr[low:high]

arraycopy(tempArr, 0, array, p, tempArr.length);

  

return array;

}

/*

*

* n: the size of the output array

*

* k: the maximum value in the array

*

*/

public static int[] generate_random_array(int n, int k) {

List<Integer> list;

int[] array;

Random rnd;

rnd = new Random(System.currentTimeMillis());

list = new ArrayList<Integer>();

for (int i = 1; i <= n; i++)

list.add(new Integer(rnd.nextInt(k + 1)));

Collections.shuffle(list, rnd);

array = new int[n];

for (int i = 0; i < n; i++)

array[i] = list.get(i).intValue();

return array;

}

/*

*

* n: the size of the output array

*

*/

public static int[] generate_random_array(int n) {

List<Integer> list;

int[] array;

list = new ArrayList<Integer>();

for (int i = 1; i <= n; i++)

list.add(new Integer(i));

Collections.shuffle(list, new

Random(System.currentTimeMillis()));

array = new int[n];

for (int i = 0; i < n; i++)

array[i] = list.get(i).intValue();

return array;

}

/*

*

* Input: an integer array

*

* Output: true if the array is acsendingly sorted, otherwise return

*

* false

*

*/

public static boolean check_sorted(int[] array) {

for (int i = 1; i < array.length; i++) {

if (array[i - 1] > array[i])

return false;

}

return true;

}

public static void print_array(int[] array) {

for (int i = 0; i < array.length; i++)

System.out.print(array[i] + ", ");

System.out.println();

}

public static void main(String[] args) {

// TODO Auto-generated method stub

System.out.println("Merge sort starts ------------------");

for (int n = 100000; n <= 1000000; n=n+100000) {

int[] array = Sort2.generate_random_array(n);

//Sort.print_array(array);

long t1 = System.currentTimeMillis();

array = Sort2.merge_sort(array, 0, n-1);

long t2 = System.currentTimeMillis();

long t = t2 - t1;

//Sort.print_array(array);

boolean flag = Sort2.check_sorted(array);

System.out.println(n + "," + t + "," + flag);

}

System.out.println("Merge sort ends ------------------");

}

}

=======================================
See Output, Sorted using Merge Sort

3 import java.util.*; 4 5 public class Sort2 [ public static int[merge_sortCint array, int p, int r)1 10 // Check if low is smaller then high, if not then the array is sorted if(p<r){ 12 13 14 15 16 er 17 18 19 20 21 // Get the index of the element which is in the middle int middle (p r) 2; // Sort the left side of the array merge-sort(array,p, middle) ; // Sort the right side of the array merge_sort(array,middle + 1, r); /Combine them both merge(array,p, middle, r); jav Console X <terminated> Sort2 [Java Application] /Library/Java/JavaVirtualMachines/jdk1.8.0-181.jdk/Contents/Home/bin/java (29-Jan-2019 Merge sort starts - 100000,36,true 200000,46,true 300000,53,true el 400000,63,true 500000,87,true 600000,94,true 700000,115,true 800000,147,true 900000,152,true 1000000,178,true Merge sort ends -

RATE THUMBSUP PLEASE

THANKS