INSTRUCTIONS: Complete the following java code following the comment and TODO lines package hw1;

public class HW1 {

/** * @param args the command line arguments */ static Random rand = new Random();

/** * @param args the command line arguments */ public static void main(String[] args) { // Sign on out.println("CPS HW Asgn 1 by ____Your name here____"); // Demonstrate that the sorts work and show sample comparison counts demoBubbleSort(); demoMergeSort(); // Collect comparison counts for sorting random arrays using both // sorting techniques for arrays of various sizes and report (2 sets) collectAndPrintData(); collectAndPrintData(); out.println(" HW Asgn 1 complete."); } // end main

private static void demoBubbleSort() { int arr[] = {16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; int brr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}; // TODO: Sort these arrays using bubble sort, show original and sorted // arrays and the comparison counts (see sample output)

} // end method

private static void demoMergeSort() { int arr[] = {16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; int brr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}; int crr[] = {8, 15, 10, 13, 12, 9, 11, 14, 16, 4, 5, 6, 7, 1, 3, 2}; // TODO: Sort these arrays using merge sort, show original and sorted // arrays and the comparison counts (see sample output)

} // end method

private static void collectAndPrintData() { // TODO: print the section and table column headers // TODO: for arrays of size 1000 to 10000, create two copies of // the same random array, sort one by bubble sort, the other by // merge sort, print array size and the two comparison counts // as one row of data in the table

} // end method

// optimized bubble sort as described in the handout private static int bubbleSort(int[] arr) { int compCount = 0; // comparison counter // declare any other variables you need

// TODO: implement optimized bubble sort as described in handout

return compCount; } // end bubbleSort

// sorts an array of integers (shell function for public use) public static int mergeSort(final int[] arr) { return mergeSort(arr, 0, arr.length - 1); } // end public sort

// sort the segment arr[low:high], its length is (high - low + 1) private static int mergeSort(final int[] arr, final int low, final int high) { int compCount = 0; // counts number of comparisons made

// Base case: a segment of length

// Recursive case: segment length > 1 // Consider arr[low:high] split into arr[low:mid] and arr[mid+1:high] // and sort them recursively where mid = (low + high) / 2 // Also add up the comparison counts from sorting the two sublists

// merge arr[low:mid] and arr[mid+1:high] into arr[low:high] // add comparison count to the total above

// return the accumulated count return compCount; } // end private sort

private static int merge(final int[] arr, final int low, final int high) { // array segment arr[low:high] contains two sorted subsegments // arr[low:mid] and arr[mid+1:high] where mid = (low + high)/2 int compCount = 0; // counts number of comparisons made // TODO: declare other variables you need // TODO: code the merge process, increment the comparison counter // while both segments have values to be processed // TODO: handle the left over values from one segment, this process // does not contribute to the comparison count // TODO: copy back from the merged segment to arr[low:high] return compCount; } // end merge

// utility method, loads random integer values in an array // the caller is responsible for allocating storage for the array private static void loadRandom(int[] arr) { for (int k = 0; k

}

Output - Asgn01_Key (run) - Editor Dutput - Asgn01_Key (run) IUn: CPS 151 H\% Asgn 1 by KEY Optimal Bubble Sort comparison counts (specific arrays) Original array: [16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1] Sorted array: [1,2,3,4,5,6,7,6,9,10,11,12,13,14,15,16] Comparison count =120 Original array: [1,2,3,4,5,6,7,6,9,10,11,12,13,14,15,16] Sorted array: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] Comparison count =15 Merge Sort comparison counts (specific arrays) Original array: [16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1] Sorted array: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] Comparison count =32 Original array: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] Sorted array: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] Comparison count =32 Original array: [6,15,10,13,12,9,11,14,16,4,5,6,7,1,3,2] Sorted array: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] Comparison count =49 Bubble and Merge sort comparison counts (random arrays) Bubble and Merge sort comparison counts (random arrays)