Perform an empirical analysis of the quicksort algorithm

Assignment Help Computer Engineering
Reference no: EM132167191

Using C++, Python, or Java, write a program that:

In this programming exercise you will perform an empirical analysis of the QuickSort algorithm to study the actual average case behavior and compare it to the mathematically predicted behavior.

That is, you will write a program that counts the number of comparisons performed by QuickSort on an array of a given size.

You will run the program on a large number of arrays of a certain size and determine the average number of comparisons performed. You will do this for several different sizes and compare the observed results with what is expected.

Using C++, Python, or Java, write a program that:

prompts the user to enter the number n, of arrays to be processed and the size m, of each array

creates an array, of the given size, containing the integers between 1 and m

for the given number of arrays

randomly unsorts the array

sorts the array using the version of QuickSort developed in your text and in class

counts the number of comparisons performed during the partitioning subroutine of the sort

calculates the average number of comparisons performed in processing all the arrays

You will need to use the versions of QuickSort and Partition given in your text since that was what was used to derive the predicted average complexity you will be comparing your results with.

The program should output the number of arrays processed, the size of the arrays processed and the average number of comparisons per array.

For example, if the user enters 50 and 100 the output would be similar to:

# of arrays processed: 50

# of items in each array: 100

average number of comparisons: 926.02 (Your results may be different!)

The following algorithm can be used to unsort an array A, of size m.

1) FOR i := 1 to m

2) Generate a random number r, between 1 and m

3) Swap A[i] and A[r]

Use your program to determine the average number of comparisons performed in sorting 1000 arrays for each of the array sizes, 10, 50, 100, 500, 1000, 5000, 10,000, 50,000 and 100,000.

Compare the observed average with the average predicted by the derivation of the average-case time complexity in section 2.4 of your text. Display your results in a table comparing the predicted average with the observed average.

You will want to look at the percent difference between the predicted and observed values. Write a paragraph discussing your conclusions about any differences you notice and what they tell you about the actual asymptotic behavior of the quick sort.

Incremental Development

It is usually not a good idea to try to code a complicated algorithm from beginning to end. Taking a few extra minutes to create your program incrementally can save you HOURS of debugging. In developing this program, I would suggest the following approach:

Write functions that implement QuickSort and Partition as given in your text.

Write a "main" function that creates the array of exercise 19 on p. 91 and sorts it using your QuickSort function.

Add code to count the number of comparisons performed during the sort. This will require an additional parameter to both QuickSort and Partition.

Check that the number of comparisons used to sort the array of exercise 19 on p. 91 is what it should be.

Write your "unsort" function and test it thoroughly.

Change "main" so that it prompts the user for the size m, of the array, creates an array of size m that contains the integers 1 to m, unsorts it, then uses QuickSort to sort it and counts the comparisons.

Finally, change "main" so that it prompts the user for the number of arrays n, to test and prints the average number of comparisons done.

Reference no: EM132167191

Questions Cloud

Describe some aspect of the depreciation rule : Study the depreciation rules as published by the IRS or the appropriate agency of another government. Describe some aspect not covered in this chapter.
Write a program that accepts as input a sentence : Write a program that accepts as input a sentence in which all of the words are run together, but the first character of each word is uppercase.
Create a solution for implementing some kind of random : Create a solution for implementing some kind of random behavior for your student.
Determine the depreciation schedule for the equipment : A small but very profitable research firm purchased $175,000 worth of research equipment in 2003. Using MACRS and Section 179 expensing.
Perform an empirical analysis of the quicksort algorithm : Perform an empirical analysis of the QuickSort algorithm to study the actual average case behavior and compare it to the mathematically predicted behavior.
What is the macrs recovery period : A small design firm's only capital purchase this year is a graphics workstation, which will cost $28,000. The firm's taxable income currently averages.
What is the value of p : What is the value of p? What is the value of p-hat? What is the absolute value of the test statistic [Hint: don't round p or p-hat in your calculation]?
Creating dynamic websites and web-based applications : Creating Dynamic Websites and Web-based Applications - You can build any type of website you choose. For example a portfolio site, brochure site, information
Compute the annual depletion using given data : The Red Dog oil field will become less productive each year. Martinson Brothers is a small company that owns Red Dog, which is eligible for percentage depletion

Reviews

Write a Review

Computer Engineering Questions & Answers

  Mathematics in computing

Binary search tree, and postorder and preorder traversal Determine the shortest path in Graph

  Ict governance

ICT is defined as the term of Information and communication technologies, it is diverse set of technical tools and resources used by the government agencies to communicate and produce, circulate, store, and manage all information.

  Implementation of memory management

Assignment covers the following eight topics and explore the implementation of memory management, processes and threads.

  Realize business and organizational data storage

Realize business and organizational data storage and fast access times are much more important than they have ever been. Compare and contrast magnetic tapes, magnetic disks, optical discs

  What is the protocol overhead

What are the advantages of using a compiled language over an interpreted one? Under what circumstances would you select to use an interpreted language?

  Implementation of memory management

Paper describes about memory management. How memory is used in executing programs and its critical support for applications.

  Define open and closed loop control systems

Define open and closed loop cotrol systems.Explain difference between time varying and time invariant control system wth suitable example.

  Prepare a proposal to deploy windows server

Prepare a proposal to deploy Windows Server onto an existing network based on the provided scenario.

  Security policy document project

Analyze security requirements and develop a security policy

  Write a procedure that produces independent stack objects

Write a procedure (make-stack) that produces independent stack objects, using a message-passing style, e.g.

  Define a suitable functional unit

Define a suitable functional unit for a comparative study between two different types of paint.

  Calculate yield to maturity and bond prices

Calculate yield to maturity (YTM) and bond prices

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd