Please do the following problem, the code must be written in JAVA.
1. Implement a main method that calls 2 methods, measuring the running time of each. Specifically, your program must prompt the user to enter the size of the input n and the expected number of repeti- tions r. Then, create TWO separate arrays of n doubles containing the SAME numbers. Each number should be chosen uniformly at random from the interval [0, 1], and choose its number of repetitions also at random but in the range [1, 2r] (so the expected is r). Then, call one sorting method in each array, and output the running time taken by each. Notice that it is crucial to create two separate arrays with the same content. Indeed, if they had different content the comparison could be unfair, and if we had only one array with two references we would be sorting a sorted array when we call the second method (recall that arrays are passed by reference). Implement two sorting methods: Quick Sort, and Bucket Sort. Each method must receive the array produced by the main method as a parameter and sort it. The pseudocode for Quick Sort and Bucket Sort is attached. Test the algorithms with different values of n and r and fill TWO tables like the following with the running times measured (put the table in the code header). 2. 3. ni n2 n3 na ns 116 12 73 TA 75 76 To choose your input values n and r, stretch your code with values of n and r as large as possible, before you run out of memory or the execution takes just too long. Then, come down to smaller values. You should have a combination of small/large n's and small/large r's. If possible, you should try to find values for which you can distinguish better performance for each. Based on the running times observed, draw conclusions about the experimental performance. Are both algorithms always sim- ilar? Do the repetitions have an impact? Justify based on your mea- surements, not in the theoretical upper bound. Provide your answers in the remarks section of the code header. 4. 1. Implement a main method that calls 2 methods, measuring the running time of each. Specifically, your program must prompt the user to enter the size of the input n and the expected number of repeti- tions r. Then, create TWO separate arrays of n doubles containing the SAME numbers. Each number should be chosen uniformly at random from the interval [0, 1], and choose its number of repetitions also at random but in the range [1, 2r] (so the expected is r). Then, call one sorting method in each array, and output the running time taken by each. Notice that it is crucial to create two separate arrays with the same content. Indeed, if they had different content the comparison could be unfair, and if we had only one array with two references we would be sorting a sorted array when we call the second method (recall that arrays are passed by reference). Implement two sorting methods: Quick Sort, and Bucket Sort. Each method must receive the array produced by the main method as a parameter and sort it. The pseudocode for Quick Sort and Bucket Sort is attached. Test the algorithms with different values of n and r and fill TWO tables like the following with the running times measured (put the table in the code header). 2. 3. ni n2 n3 na ns 116 12 73 TA 75 76 To choose your input values n and r, stretch your code with values of n and r as large as possible, before you run out of memory or the execution takes just too long. Then, come down to smaller values. You should have a combination of small/large n's and small/large r's. If possible, you should try to find values for which you can distinguish better performance for each. Based on the running times observed, draw conclusions about the experimental performance. Are both algorithms always sim- ilar? Do the repetitions have an impact? Justify based on your mea- surements, not in the theoretical upper bound. Provide your answers in the remarks section of the code header. 4
