Tukey proposed an idea to find a better median in random arrats so that quick sort uses less comparisons to get approximate median of 9 items in the arrays. This assignment to test if a quick sort backed by "Tukey's ninther's idea" is faster than regular quick sort algorithm. You need to compare these two approaches in the sorting of randomly created same 32K char items in arrays. Repeat the comparison 300 times keeping running time of each approach. In your analysis, report
- Average running time of Tukey's approach and Regular QSort.
- Standard deviation of running time of Tukey's approach and Regular QSort.
- How many time Tukey's approach is faster than regular QSort.
- Is Tukey's idea significantly faster than regular quick sort? What is p-value? (Assuming run times are normally distributed, use t-test to compare their normal distributions. Please see [login to view URL] )
Submit a .cpp file with your code. On the top of you cpp file, report above metrics as comments.
4 freelancers are bidding on average $48 for this job
Hi there! As I have good knowledge of algorithm and mathematics including probability and statistics, I'm interested in your project. We can discuss further via chat. Regards.