Reference no: EM132403070
Exercise
We have been hired to design and implement a digital music streaming service called Potify, where users can listen to songs and add them as favourite to their personal library. As part of our job, we have to implement the searching and sorting of songs.
Users will only be able to sort songs using the same criteria of song title and author (as in Exercise 3d).
The team of engineers you manage has developed two sorting algorithms that have to be tested. The first one is a variant of MergeSort, whereas the other is a variant of QuickSort. Moreover, the development team also wants to compare these variants with the algorithm already implemented in the Java Arrays class, called parailelSort.
For this exercise you must implement an experimental test about each of the algorithm's computing time:
• You will have to test different array sizes: 10, 100, 1000, 10000, 1000000,10000000.
• For each array size, you must generate 30 distinct array instances of each size (check how you can generate random song collections in the provided class) and calculate the average time the algorithm takes in order to solve problems of that size.
• After executing the experiments (they can take hours), you must determine and justify which of the sorting algorithms works best (you can use charts). On the other hand, you must compare the experimental cost of MergeSort, QuickSort and Arrays.parallelSort with the theoretical temporal cost (for instance, you can plot the theoretical cost as a baseline in the chart).
• Explain how the algorithm used in the Arrays.parallelSort() method works, and justify whether the performance you get in your experiment is the expected in all scenarios. You can take a look at the ArraysParallelSortHelpers class which this method uses.
In order to complete this exercise you will have to modify a code skeleton to achieve your objective. The results of the experiment are automatically stored in the out/test/resources/benchmark resufts.tsv file on your project. The algorithms should compare in the most similar conditions so as the comparison is fair enough.