logo Use CA10RAM to get 10%* Discount.
Order Nowlogo
(5/5)

How many time Tukey\'s approach is faster than 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.

 

(5/5)
Attachments:

Expert's Answer

333 Times Downloaded

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

333 Times Downloaded

Ask This Question To Be Solved By Our ExpertsGet A+ Grade Solution Guaranteed

expert
Atharva PatilComputer science

846 Answers

Hire Me
expert
Chrisantus MakokhaComputer science

513 Answers

Hire Me
expert
AyooluwaEducation

699 Answers

Hire Me
expert
RIZWANAMathematics

769 Answers

Hire Me

Get Free Quote!

358 Experts Online