AssignmentCOMP2080 Assignment 1 (10%) Due: 6th March 2022 11:30PM Given: 13th February 2022 Submission Instructions: 1) Fill in your full name and student number in the spaces provided further down this page. 2) Fill in all results into the tables provided. 3) Paste the code for each class and main program into this document after the question. 4) Upload this document to blackboard . · You must have your name and student ID number commented in all code submitted. Failure to do this will result in a loss of marks. · All submissions should at least compile. · Non-compiling assignments will NOT be marked and will be given a grade of 0. · All your submissions should be suitably documented. Name :_________________ Student ID:_________________ Description: The purpose of this question is to allow the student to independently compare the run time of various sorting and searching algorithms. This will allow the student to get a better understanding of time complexity. It also aims to build an appreciation of the effects that the size and organization of data have on the speed of algorithms. The sorting algorithms that will be examined are: a) Selection sort b) Insertion sort c) Merge sort d) Quick Sort All sorting algorithms must sort the arrays in descending order. Each sorting and searching algorithm will be comparatively run on arrays of the following sizes: 1. fifty (50) 2. one thousand (1,000) 3. ten thousand (10,000) 4. one hundred thousand (100,000) 5. one million (1,000,000) Each sort and search is to be tested on the same data set to strive for some consistency. Sorting Methodology and Requirements: 1. Create a core data set called “coreData” which must be a single array of size one million (1,000,000) integers filled with random numbers between one (1) and two million (2,000,000). 2. For each comparative sorting test, four (4) copies (one for each sort to be tested) consisting of the same data from “coreData” must be made. For example, if the comparative test is on one thousand (1,000) elements, four arrays of size (1000) should be made and filled with a copy of the first one thousand (1000) elements of “coreData”. All recorded times must be measured using System.nanoTime() for consistency. An example of how to use it is given below. long start = System.nanoTime(); //code to be tested long end = System.nanoTime(); long timeTaken = end – start; Test data size Time unit 50 nanoseconds 1,000 nanoseconds 10,000 nanoseconds 100,000 nanoseconds 1,000,000 milliseconds The unit for printing the time must be done according to the following table: Output requirements: The name of each sorting algorithm tested and the time it took to sort the data must be shown grouped by the test data size. For example if the test data size is fifty (50), the time taken for all the sorting algorithms to sort the data must be shown one after another. Fill in the tables below with the results of your tests. Sorting Comparison Number of Items Selection Sort 50 1,000 10,000 100,000 1,000,000 Run 1 Run 2 Run 3 Run 4 Run 5 Average Number of Items Insertion Sort 50 1,000 10,000 100,000 1,000,000 Run 1 Run 2 Run 3 Run 4 Run 5 Average Number of Items Merge Sort 50 1,000 10,000 100,000 1,000,000 Run 1 Run 2 Run 3 Run 4 Run 5 Average Number of Items Quick Sort 50 1,000 10,000 100,000 1,000,000 Run 1 Run 2 Run 3 Run 4 Run 5 Average Searching Methodology and Requirements: 1. Create a core data set called “coreData” which must be a single array of size one million (1,000,000) integers filled with random numbers between one (1) and two million (2,000,000). This array must then be sorted in descending order. (You may use the sorted array from the first part). 2. For each comparative search test, you must search for the number 2,500,000 (two million five hundred thousand). This number does not exist in the array and represents the worst case for both searches. You must repeat the tests 5 times with binary search and linear search, timing how long it takes to complete for each dataset size. Place the results in the table below. All recorded times must be measured using System.nanoTime() for consistency. Fill in the tables below with the results of your tests. Searching Comparison Number of Items Binary Search 50 1,000 10,000 100,000 1,000,000 Run 1 Run 2 Run 3 Run 4 Run 5 Average Number of Items Linear Search 50 1,000 10,000 100,000 1,000,000 Run 1 Run 2 Run 3 Run 4 Run 5 Average PASTE YOUR CLASSES FOR THE ASSIGNMENT AND MAIN HERE: Your code must have your name commented in each new class.