Average running time in millisecond of Tukey\'s approach and regular Quick Sort.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Tukey's ninther

Tukey proposed an idea (see quick sort lecture slides) to find a better median in random arrays so that quick sort uses less comparisons. It gets approximate median of 9 items from the data array to find a pivot item. This assignment to test if a quick sort initiated with "Tukey's ninther's " is faster than regular quick sort algorithm. You need to compare these two approaches in the sorting of 256K 4-char strings, randomly created between aaaa - ZZZZ. Random strings has only a-z, A-Z letters.

Repeat the comparison 100 times and report

 

- Average running time in millisecond of Tukey's approach and regular Quick Sort.

 

- How many time Tukey's approach is faster than regular Quick Sort.

 

- What is t-value? Assuming run times are normally distributed with same variance, use t-test to compare their normal distributions. Please see https:/ en.wikipedia.org/wiki/Student%27s_t- test#Independent_two-sample_t-test

Your program should report above metrics as output, similar to

 

Tukey QS Ave: 125 ms, Reg. QS: 129 ms Tukey QS was faster in 51% of 100 runs. T-value for two distributions is 2.26.

Hint: Do not forget to randomize the data; and make sure that both algorithms sorts same data for comparison.

You can see how Tukey's ninther is used in a java implementation here.

Do not include unnecessary headers and functions. Code syntax will be graded.

 

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of