1 / 3 81% +] [G] Your objective is to implement the following three algorithms: From the list of quadratic time algorithms: Cocktail Sort From the list of linearithmic time algorithms: Quick Sort From the list of linear time algorithms: Counting Sort All of these algorithms are explained in detail in the notes and some or all of the pseudocode behind them is given. You are to implement the algorithm as described in the lecture notes. Each of these algorithms should be done in a separate function. There is no template or .class files for this. Everything is done by you. You must have a Main class that has the entry point, but you are free to have other classes if you want. You could have a different class for each sorting method, a single class that has three methods for the three different sorts, or you could put three methods inside the Main class for sorting. You decide. You must have a public class in its own file called Main. This public class will contain the entry point which must do the following: First generate an array of 20 ints, each ranging from 0 to 150 (inclusively) o You will need to look online to figure out how to generate random numbers in a range with Java Make three exact copies of that array o Make sure you have three copies and not three variables that point to the same copy. This is an important distinction to make. Send each sorting method its own copy of the array This is so each sorting algorithm can start with the same array contents Print out the original array of ints Print out the sorted array of ints after applying each sorting method o See the Sample Output below for more clarification Now generate an array of 20,000 ints each within the same value range as above (i.e. O to 150) There will be duplicate keys, but this should not pose a problem for your algorithms Make three exact copies of this large array Now use Java to time each algorithm as it runs through its copy of the array o You are going to have to look up online how to use Java to get the exact runtime of a block of code o It is VERY IMPORTANT that you do NOT include the allocation, initialization or cloning of the array of ints in your timing. The only thing I want you to time is the sorting algorithm itself (and maybe the function call to the sorting algorithm). When the algorithm is done (function returns back to main), record the time and move on to timing the next algorithm Show the times each algorithm took (in milliseconds) o Obviously, we should see Cocktail sort taking the longest amount of time while Counting sort takes the least. Quick sort should be somewhat close to the runtime of Counting sort. Sample Output: Your output should look exactly like the following (albeit with different numbers for your list and different numbers for your times). Your timings might be different, but they should still be within reason. For example, I expect Cocktail to be in the triple digits, Quick to be in the single or low double digits, and Counting to be the fastest in the mid to low single digits. If your timings do not fall within this range, this is an indication that something is not working right or you aren't timing right. Please ask me for help if you can't figure it out. The spacing, values for n, text, etc must be the same. $ javac Main.java && java Main TESTING with n = 20 Original List: 76 91 129 92 0 67 40 57 43 2 58 120 57 67 4 138 31 56 117 41 Cocktail sorted: 0 2 4 31 40 41 43 56 57 57 58 67 67 76 91 92 117 120 129 138 Quick sorted: 0 2 4 31 40 41 43 56 57 57 58 67 67 76 91 92 117 120 129 138 Counting sorted: 0 2 4 31 40 41 43 56 57 57 58 67 67 76 91 92 117 120 129 138 TIMING with n = 20,000 Cocktail took 759.28 ms Quick took 8.47 ms Counting took 4.63 ms Note: Use the demo_all.jar file on Moodle for help (labelled as for all other data structures and algs in the Visualizations section). Run it with java -jar demo_all.jar and play around with the different sorting methods (mainly cocktail, quick and counting for this assignment). Make sure you fully understand the algorithms. You cannot even begin to properly implement something until you fully understand it. Blindly converting the pseudocode from the notes into Java will not be enough. The sorting algorithms I am asking you to implement are decently popular. It is possible that you can find Java implementations already online. Let me be clear about this. If you grab an implementation from an online source and try to pass it off as your own, you will receive the penalty for cheating on this assignment. You are to write each sort yourself following the algorithm from the lecture notes. Cocktail Sort Introducing cocktail shaker sort (or just cocktail sort). Bubble sort will move large values to the end of the list very quickly. Yet smaller values will move to the front of the list very slowly. In fact we refer to the fast moving values (the larger values in the case of bubble sort) as "rabbits" and the slow moving values (the smaller values) as "turtles", based on the old tortoise and hare story. So the rabbits move fast, but the turtles move slowly. This is a problem since a small value at the end of the list will prevent an early exit, even if the rest of the list becomes sorted after the first few passes! What if we could make them both rabbits? This would mean large values quickly move to the end of the list and small values quickly move to the front. Both small and large values would become rabbits. Now an early exit due to no swaps during a pass will have a much more likely chance of occurring early on, as both large and small values will move quickly to their desired locations. This isn't likely to help our asymptotic bounds (i.e. our Big Oh time complexity) but, in practice, it should speed things up. 2 Cocktail sort runs bubble sort from front to back, but then runs it again from back to front. It continues ping- ponging like this a total of ((n-1)/2) times. A single pass in cocktail sort is considered to be one round trip (front to back then back to front). This is easy to write in pseudocode: list + values to sort n length of the list for it i to (n - 1) / 2 + 1 // forward direction anyswapsMade = false for je i to (n - i) if list at j = 0 and list at right > list at pivot Pos right + right - 1 end if left >= right then break else swap list values at left and right left + left + 1 right + right - 1 end end swap list values at right and pivot Pos return right end Counting Sort Up until now we have only handled comparison sorts. This algorithm, however, works without making any comparisons. As a side note, it can actually be mathematically proven-2 that any comparison sorting algorithm can do no better than linearithmic time in its worst case. This means it is just not possible to go faster than o (n lg n) for any algorithm using comparisons to sort. To go faster, we must do away with comparisons. Here's the counting sort algorithm: list + values to sort nt length of the list // allocate count array and initialize to all zeros count(max value in list + 1] + all zeros // calculate the histogram of key frequencies for it 0 ton count[list at i] + count[list at i] + 1 next // calculate the starting index for each key total = 0 for it to length of count array oldCount + count at i count at it total total + total + oldCount next // allocate output array output[n] // copy to output array, keeping order of inputs with equal keys (aka stable sort) for it 0 ton value = list at i output at (count at value) + value count at value + count at value + 1 next https://www.geeksforgeeks.org/lower-bound-on-comparison-based-sorting-algorithms/ https://www.quora.com/How-do-l-prove-that-a-comparison-based-sort-of-a-length-N-array-cannot-be-done-in-O-N-time-in-the- worst-case // copy back to original list for it 0 ton list at it output at i next 1 / 3 81% +] [G] Your objective is to implement the following three algorithms: From the list of quadratic time algorithms: Cocktail Sort From the list of linearithmic time algorithms: Quick Sort From the list of linear time algorithms: Counting Sort All of these algorithms are explained in detail in the notes and some or all of the pseudocode behind them is given. You are to implement the algorithm as described in the lecture notes. Each of these algorithms should be done in a separate function. There is no template or .class files for this. Everything is done by you. You must have a Main class that has the entry point, but you are free to have other classes if you want. You could have a different class for each sorting method, a single class that has three methods for the three different sorts, or you could put three methods inside the Main class for sorting. You decide. You must have a public class in its own file called Main. This public class will contain the entry point which must do the following: First generate an array of 20 ints, each ranging from 0 to 150 (inclusively) o You will need to look online to figure out how to generate random numbers in a range with Java Make three exact copies of that array o Make sure you have three copies and not three variables that point to the same copy. This is an important distinction to make. Send each sorting method its own copy of the array This is so each sorting algorithm can start with the same array contents Print out the original array of ints Print out the sorted array of ints after applying each sorting method o See the Sample Output below for more clarification Now generate an array of 20,000 ints each within the same value range as above (i.e. O to 150) There will be duplicate keys, but this should not pose a problem for your algorithms Make three exact copies of this large array Now use Java to time each algorithm as it runs through its copy of the array o You are going to have to look up online how to use Java to get the exact runtime of a block of code o It is VERY IMPORTANT that you do NOT include the allocation, initialization or cloning of the array of ints in your timing. The only thing I want you to time is the sorting algorithm itself (and maybe the function call to the sorting algorithm). When the algorithm is done (function returns back to main), record the time and move on to timing the next algorithm Show the times each algorithm took (in milliseconds) o Obviously, we should see Cocktail sort taking the longest amount of time while Counting sort takes the least. Quick sort should be somewhat close to the runtime of Counting sort. Sample Output: Your output should look exactly like the following (albeit with different numbers for your list and different numbers for your times). Your timings might be different, but they should still be within reason. For example, I expect Cocktail to be in the triple digits, Quick to be in the single or low double digits, and Counting to be the fastest in the mid to low single digits. If your timings do not fall within this range, this is an indication that something is not working right or you aren't timing right. Please ask me for help if you can't figure it out. The spacing, values for n, text, etc must be the same. $ javac Main.java && java Main TESTING with n = 20 Original List: 76 91 129 92 0 67 40 57 43 2 58 120 57 67 4 138 31 56 117 41 Cocktail sorted: 0 2 4 31 40 41 43 56 57 57 58 67 67 76 91 92 117 120 129 138 Quick sorted: 0 2 4 31 40 41 43 56 57 57 58 67 67 76 91 92 117 120 129 138 Counting sorted: 0 2 4 31 40 41 43 56 57 57 58 67 67 76 91 92 117 120 129 138 TIMING with n = 20,000 Cocktail took 759.28 ms Quick took 8.47 ms Counting took 4.63 ms Note: Use the demo_all.jar file on Moodle for help (labelled as for all other data structures and algs in the Visualizations section). Run it with java -jar demo_all.jar and play around with the different sorting methods (mainly cocktail, quick and counting for this assignment). Make sure you fully understand the algorithms. You cannot even begin to properly implement something until you fully understand it. Blindly converting the pseudocode from the notes into Java will not be enough. The sorting algorithms I am asking you to implement are decently popular. It is possible that you can find Java implementations already online. Let me be clear about this. If you grab an implementation from an online source and try to pass it off as your own, you will receive the penalty for cheating on this assignment. You are to write each sort yourself following the algorithm from the lecture notes. Cocktail Sort Introducing cocktail shaker sort (or just cocktail sort). Bubble sort will move large values to the end of the list very quickly. Yet smaller values will move to the front of the list very slowly. In fact we refer to the fast moving values (the larger values in the case of bubble sort) as "rabbits" and the slow moving values (the smaller values) as "turtles", based on the old tortoise and hare story. So the rabbits move fast, but the turtles move slowly. This is a problem since a small value at the end of the list will prevent an early exit, even if the rest of the list becomes sorted after the first few passes! What if we could make them both rabbits? This would mean large values quickly move to the end of the list and small values quickly move to the front. Both small and large values would become rabbits. Now an early exit due to no swaps during a pass will have a much more likely chance of occurring early on, as both large and small values will move quickly to their desired locations. This isn't likely to help our asymptotic bounds (i.e. our Big Oh time complexity) but, in practice, it should speed things up. 2 Cocktail sort runs bubble sort from front to back, but then runs it again from back to front. It continues ping- ponging like this a total of ((n-1)/2) times. A single pass in cocktail sort is considered to be one round trip (front to back then back to front). This is easy to write in pseudocode: list + values to sort n length of the list for it i to (n - 1) / 2 + 1 // forward direction anyswapsMade = false for je i to (n - i) if list at j = 0 and list at right > list at pivot Pos right + right - 1 end if left >= right then break else swap list values at left and right left + left + 1 right + right - 1 end end swap list values at right and pivot Pos return right end Counting Sort Up until now we have only handled comparison sorts. This algorithm, however, works without making any comparisons. As a side note, it can actually be mathematically proven-2 that any comparison sorting algorithm can do no better than linearithmic time in its worst case. This means it is just not possible to go faster than o (n lg n) for any algorithm using comparisons to sort. To go faster, we must do away with comparisons. Here's the counting sort algorithm: list + values to sort nt length of the list // allocate count array and initialize to all zeros count(max value in list + 1] + all zeros // calculate the histogram of key frequencies for it 0 ton count[list at i] + count[list at i] + 1 next // calculate the starting index for each key total = 0 for it to length of count array oldCount + count at i count at it total total + total + oldCount next // allocate output array output[n] // copy to output array, keeping order of inputs with equal keys (aka stable sort) for it 0 ton value = list at i output at (count at value) + value count at value + count at value + 1 next https://www.geeksforgeeks.org/lower-bound-on-comparison-based-sorting-algorithms/ https://www.quora.com/How-do-l-prove-that-a-comparison-based-sort-of-a-length-N-array-cannot-be-done-in-O-N-time-in-the- worst-case // copy back to original list for it 0 ton list at it output at i next