Submission Requirements Complete the following exercise and submit electronically in the assignments folder on eLearn as...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Submission Requirements Complete the following exercise and submit electronically in the assignments folder on eLearn as an IntelliJ Project - Zip the entire folder not just the source files in MyCanvas. Please refer the course Calendar for the exact date and time of the submission. This assignment is to be completed individually. Background You are to evaluate the Sort Algorithms that were presented in class for efficiency. You have been provided with starter code (see MyCanvas) that includes the source code for each of the sort methods discussed (bubble, selection, insertion, merge and quick) that are to be evaluated. You must add code to each of the methods to count the number of comparisons required to completely sort the data. Ensure that you generate and use the same data for each sort. You will also measure the time required to sort the data using each method by timing the algorithm using the System.nanotime method. Requirements Your program must report the following information: 1. The time required in nanoseconds, the number of comparisons required and the time to execute a basic step (the comparison) in ns for each of the sort methods provided. The basic step is determined by taking the time required to sort an array of a size n and dividing by the number of comparisons required for that algorithm. Report your results for data sets of 30, 300, 30000 elements. 2. Modify the sorta, sortb, sortc, sortd, sorte methods to count the number of comparisons and return this value from the method. Suggested Steps: a. Change each of the sort methods from type void to type int. b. Add a local count variable to each method. c. Increment the count just before the comparison of two array elements in each of the sort methods. d. Return the count value from the method and print to the screen in the main method. 3. The sorta method currently counts the # of comparisons by using a global variable. This is not a good programming technique. Modify the sorta method to count comparisons by passing a parameter. This is a little trickier as the comparisons are done in the part method. You should notice that the number of comparisons can be determined before the call to the part method. You will need to return this value from the sorta method and modify the sorta header to pass this value into each recursive call. You will need to add the counts recursively. As an alternative to the recursive counting, you can leave the code as is and complete the sorta counting using the global variable. 4. Adding counting to the sortd method. Again, you can use a recursive technique or use a global variable. Recursive counting is preferred. If this is not possible use a global variable like sorta 5. Time the java standard Arrays. sort method for all three sizes. 6. In a Comment section at the TOP of your source file, provide answers to the following: Identify the type of sorts for each of the methods provided. Indicate which sort (a,b,c,d,e) is bubble, quick, merge, selection or insertion. O List in order (fastest to slowest) your selection of algorithm to use when the array to be sorted contains 30 elements. Base this on your results List in order (fastest to slowest) your selection of algorithm to use when the array to be sorted contains 30000 elements. O O O O List the algorithm and the BIG O notation (time complexity, average case) for that algorithm. Does the Big O notation line up with your results for 30000 elements? Which algorithm has the best performance of the basic step? Does this have any impact on your selection of fastest algorithm when sorting an array of 30000 elements? Why? For the standard Arrays. sort method, which algorithm do the performance results most resemble. Example Output Lab#2 Sorting Algorithm Performance Analysis Comparison for array size of 30 Number of compares for sort a Number of compares for sort b Number of compares for sort c Number of compares for sort d Number of compares for sort e Repeat for array sizes of 300 and 30000 Marking Scheme Program Modifications - Counting implemented, recursive counting implemented - 20% Program structure - Comments, follows best programming practices - 20% Output displayed for 30, 300, 30000 elements correct - 20% Discussion in comment at top of code - Questions answered based on results - 40% time = time time time = time = ns Basic Step ns Basic Step ns Basic Step ns Basic Step ns Basic Step ns ns. ns. ns ns. Submission Requirements Complete the following exercise and submit electronically in the assignments folder on eLearn as an IntelliJ Project - Zip the entire folder not just the source files in MyCanvas. Please refer the course Calendar for the exact date and time of the submission. This assignment is to be completed individually. Background You are to evaluate the Sort Algorithms that were presented in class for efficiency. You have been provided with starter code (see MyCanvas) that includes the source code for each of the sort methods discussed (bubble, selection, insertion, merge and quick) that are to be evaluated. You must add code to each of the methods to count the number of comparisons required to completely sort the data. Ensure that you generate and use the same data for each sort. You will also measure the time required to sort the data using each method by timing the algorithm using the System.nanotime method. Requirements Your program must report the following information: 1. The time required in nanoseconds, the number of comparisons required and the time to execute a basic step (the comparison) in ns for each of the sort methods provided. The basic step is determined by taking the time required to sort an array of a size n and dividing by the number of comparisons required for that algorithm. Report your results for data sets of 30, 300, 30000 elements. 2. Modify the sorta, sortb, sortc, sortd, sorte methods to count the number of comparisons and return this value from the method. Suggested Steps: a. Change each of the sort methods from type void to type int. b. Add a local count variable to each method. c. Increment the count just before the comparison of two array elements in each of the sort methods. d. Return the count value from the method and print to the screen in the main method. 3. The sorta method currently counts the # of comparisons by using a global variable. This is not a good programming technique. Modify the sorta method to count comparisons by passing a parameter. This is a little trickier as the comparisons are done in the part method. You should notice that the number of comparisons can be determined before the call to the part method. You will need to return this value from the sorta method and modify the sorta header to pass this value into each recursive call. You will need to add the counts recursively. As an alternative to the recursive counting, you can leave the code as is and complete the sorta counting using the global variable. 4. Adding counting to the sortd method. Again, you can use a recursive technique or use a global variable. Recursive counting is preferred. If this is not possible use a global variable like sorta 5. Time the java standard Arrays. sort method for all three sizes. 6. In a Comment section at the TOP of your source file, provide answers to the following: Identify the type of sorts for each of the methods provided. Indicate which sort (a,b,c,d,e) is bubble, quick, merge, selection or insertion. O List in order (fastest to slowest) your selection of algorithm to use when the array to be sorted contains 30 elements. Base this on your results List in order (fastest to slowest) your selection of algorithm to use when the array to be sorted contains 30000 elements. O O O O List the algorithm and the BIG O notation (time complexity, average case) for that algorithm. Does the Big O notation line up with your results for 30000 elements? Which algorithm has the best performance of the basic step? Does this have any impact on your selection of fastest algorithm when sorting an array of 30000 elements? Why? For the standard Arrays. sort method, which algorithm do the performance results most resemble. Example Output Lab#2 Sorting Algorithm Performance Analysis Comparison for array size of 30 Number of compares for sort a Number of compares for sort b Number of compares for sort c Number of compares for sort d Number of compares for sort e Repeat for array sizes of 300 and 30000 Marking Scheme Program Modifications - Counting implemented, recursive counting implemented - 20% Program structure - Comments, follows best programming practices - 20% Output displayed for 30, 300, 30000 elements correct - 20% Discussion in comment at top of code - Questions answered based on results - 40% time = time time time = time = ns Basic Step ns Basic Step ns Basic Step ns Basic Step ns Basic Step ns ns. ns. ns ns.
Expert Answer:
Answer rating: 100% (QA)
Lets begin by completing the SortedLinkedList class Heres the updated code for the SortedLinkedList The previous part of SortedLinkedList class remains unchanged The add method adds an element in sort... View the full answer
Related Book For
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill
Posted Date:
Students also viewed these programming questions
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
Managing Scope Changes Case Study Scope changes on a project can occur regardless of how well the project is planned or executed. Scope changes can be the result of something that was omitted during...
-
Question 4: Artistic Hand for engineering Services was formed on Jun 1, 2018. The following transactions took place during the month of Jun: I The owner invested $20,000 cash in business. 2 Hired an...
-
Auditors perform a number of procedures relating to cash-some unique, some not unique. For each substantive procedure below, identify its primary objective or indicate that the procedure serves no...
-
A home business examines its monthly production costs and sales and finds the cost function when x items are produced is given by: C(x) = 1873 +40x - 0.021x2 (in dollars) and the price each item can...
-
For the goodness-of-fit test to be valid, each of the _______________ frequencies must be at least 5. In Exercises 9 and 10, fill in each blank with the appropriate word or phrase.
-
In January 2010, Cordova Company entered into a contract to acquire a new machine for its factory. The machine, which has a cash price of $215,000, was paid for as follows: Down payment...
-
(b) Let us evaluate the proposal that you borrow rather than pay cash using present value calculations. Do this by calculating the present value of your car payments if you pay cash (that is just the...
-
The Case Study - "Lemonade: Delighting Insurance Customers with AI and Behavioral Economics". 1. How do you explain the phenomenal growth experienced by Lemonade? 2. Does Lemonade create a unique...
-
The list of numbers is to be sorted in descending order. Use the bubble sort to obtain the sorted list. Giving the state of the list after complete the pass. 35 26 45 19 74 56 44 What is the best...
-
a) If x t logt and y= log find dy at t=1. dx b) Differentiate sinx with respect to logx.
-
Write the number in standard form. 16--192 4
-
On December 1, Jasmin Ernst organized Ernst Consulting. On December 3, the owner contributed $84,780 in assets in exchange for its common stock to launch the business. On December 31, the company's...
-
2) Assume that your widget manufacturing company has a total annual demand of N widgets per year evenly distributed across the year. Each widget cost $b dollars in material and manufacturing costs to...
-
What are the perils associated with ocean and air shipments? What are the reasons for supply chain disruptions and how they can be avoided? Answer the following questions after reading the article...
-
Question3 Imagine an economy with only two goods: pizza and pasta. If pizza is represented by 2, and pasta is represented by y, and the utility function is a standard CES function: U(x, y) = (ax...
-
In the synthesis of the keto acid just given, the dicarboxylic acid decarboxylates in a specific way; it gives Explain. HO rather than HO
-
Please answer the following questions regarding the taxability of Social Security: a. A 68-year-old taxpayer has $20,000 in Social Security income and $100,000 in tax-free municipal bond income. Does...
-
Mallory Corporation has a calendar year-end. The corporation has paid estimated payments of $10,000 during 2012 but still owes an additional $5,000 for its 2012 tax year. a. When is the 2012 tax...
-
Bill and Guilda each own 50 percent of the stock of Radiata Corporation, an S corporation. Guilda's basis in her stock is $25,000. On July 31, 2012, Bill sells his stock, with a basis of $40,000, to...
-
The median is resistant because it is not affected much by_________________. In Exercises 912, fill in each blank with the appropriate word or phrase.
-
For most data sets that are skewed to the right, the mean is less than the median. In Exercises 1316, determine whether the statement is true or false. If the statement is false, rewrite it as a true...
-
The __________________ is the value in the data set that appears most frequently. In Exercises 912, fill in each blank with the appropriate word or phrase.
Study smarter with the SolutionInn App