Write a program that sorts an array of random numbers

Assignment Help Data Structure & Algorithms

Reference no: EM131159004

Write a program that sorts an array of random numbers, using the shell sort and the quick sort. Both sorts should use the same data. Each sort should be executed twice. For the first sort, fill the array with random numbers between 1 and 999. For the second sort, fill the array with a nearly ordered list. Construct your nearly ordered list by reversing elements 19 and 20 in the sorted random-number list. For each sort, count the number of comparisons and moves necessary to order this list.

Run the program three times, once with an array of 100 items, once with an array of 500 items, and once with an array of 1000 items. For the first execution only (100 elements), print the unsorted data followed by the sort data in 10-by-10 matrixes (10 rows of 10 numbers each). For all runs print the number of comparisons and the number of moves required to order the data.

To make sure your statistics are as accurate as possible, you must analyze each loop limit condition test and each selection statement in your sort algorithms. The following notes should help with this analysis:

a. All loops require a count increment in their body.

b. Pretest loops (while and for) also require a count increment either before (recommended) or after the loop to count the last test.

c. Remember that C uses the shortcut rule for evaluating Boolean and/or expressions. The best way to count them is with a comma expression, as shown below. Use similar code for the selection statements.

while ((count++, a) && (count++, b))

Analyze the statistics you generated and write a short report (less than one page) concerning what you discovered about these two sorts. Include the data in Table, one for the random data and one for the nearly ordered data. Calculate the ratio to one decimal place.

List Size	Shell	Quick	Ratio (shell/quick)
Compares
100
500
1000



Moves
100
500
1000

Table: Sorting Statistics Format for Project

Reference no: EM131159004

Questions Cloud

Report for cyber shopping project : A report for project which is cyber shopping. you just need to do references and citations for project.

Optical microscopy has mediocre resolution : Why is it nevertheless used to image small objects, instead of electron microscopes? By numerically deconvoluting optical images to cancel out the effects of diffraction (point spread function, PSF), we can gain in resolution. What "price" must be..

Write an algorithm that applies the incremental idea : Write an algorithm that applies the incremental idea of the shell sort to a selection sort. The algorithm first applies the straight section sort to items n / 2 elements apart (first, middle, and last).

What is the difference in the analysed sample volume : what is the difference in the analysed sample volume (i.e. volume of the sample from which the signal comes)?

Write a program that sorts an array of random numbers : Write a program that sorts an array of random numbers, using the shell sort and the quick sort. Both sorts should use the same data. Each sort should be executed twice.

Draw a wait-for-graph for the data above : Draw a wait-for-graph for the data above and find whether the transactions are in a deadlock or not?

What might be a concern about the use of nanotechnology : Nanotools, like the Atomic Force Microscope, allow us to build atom by atom.

What was the population of germany : What was the population of Germany in 1942? What was the population of Berlin in the same year?

What medium may be chosen for a ferrofluid for a high-vacuum : Can an aqueous solution be used? Justify...1. Give a way to confer hydrophilic behaviour to a self-assembled monolayer (SAM) coating. Or hydrophobic?

User Account

All Pages