Computer Science 282 Programming Assignment #3 As always, add whatever is necessary so that the methods...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Computer Science 282 Programming Assignment #3 As always, add whatever is necessary so that the methods below behave correctly. Leave all variables, method names, and code fragments exactly as they appear. Only add code to make the methods work. The method names should make it clear what the method should do. Ask, preferably on Canvas, if you have any questions. A few reminders and rules (ask about these if you have questions!): Your sorts should work on 0-element arrays. Shift rather than swap during insertion and trickling. Be sure your various quicksort methods are making recursive calls to the proper quicksort method. Since there are multiple quicksorts it is easy to accidentally make the wrong recursive calls. The cutoff parameter in your quicksorts represents the smallest sized partition that will be recursively sorted, as described in week 10-lecture.pdf. For example, if cutoff = 10 then a partition with 10 elements will be recursively sorted while a partition of size 9 or less will not. Be sure you get this exactly right. It is easy to be off by 1. Also, don't get thrown off by the way the calculation is done in week 10-lecture.pdf. To be sure the stack does not overflow in your quicksorts write your recursive quicksort methods with a loop that: (1) selects the pivot, (2) partitions the array by calling a partition method, (3) makes the recursive call on the smaller partition(s), and (4) sets parameter values so that the loop simulates the second/third recursive call on the larger/largest partition. The code for QS_OutsideIn_randomPivot below should prove helpful but realize that it gets a little more complicated in the 2-pivot case. When partitioning, whenever an element is encountered that is the same as the pivot assume it is in the correct spot do not move it. // Used to return the two pivots in the 2-pivot partition class Pair { public int left, right; public } } Pair(int left, int right) { this. left = left; this.right right; // Class to hold all the sorts and their associated methods class ArraySorts { public static String myName() { public static void insertionSort(int a[], int n) { public static void QS_OutsideIn_randomPivot (int a[], int n, int cutoff) { QS_OutsideIn_randomPivot (a, 0, n - 1, cutoff); insertionSort (a, n); } private static void QS_OutsideIn_randomPivot (int a[], int lf, int rt, int cutoff) { } int pivot; while ((rt - lf + 1) >= cutoff) { pivot } } = pivot = partitionOutsideIn(a, lf, rt, pivot); lf + (int) (Math.random() * (rt lf + 1)); if ((pivot - lf) < (rt - pivot)) { } } else { QS_OutsideIn_randomPivot (a, lf, pivot-1, cutoff); lf = pivot+1; QS_OutsideIn_randomPivot(a, pivot+1, rt, cutoff); pivot -1; rt = public static void QS_LeftToRight_randomPivot (int a[], int n, int cutoff) { public static void QuickSort_2Pivot_Both Random (int a[], int n, int cutoff{ public static void QS_Outside In_lfPivot (int a[], int n, int cutoff) { public static void QS_LeftToRight_lfPivot (int a[], int n, int cutoff) { public static void AlmostQS_OutsideIn_randomPivot(int a[], int n, int cutoff) { QS_OutsideIn_randomPivot (a, 0, n - 1, cutoff); public static void AlmostQS_LeftToRight_randomPivot (int a[], int n, int cutoff) { public static void AlmostQuickSort_2Pivot_BothRandom (int a[], int n, int cutoff) { public static int partitionLeftToRight (int a[], int lf, int rt, int pivot) { public static void AlmostQS_LeftToRight_randomPivot(int a[], int n, int cutoff) { a[], int n, int cutoff) { public static void AlmostQuickSort_2Pivot_BothRandom(int public static int partitionLeftToRight(int a[], int lf, int rt, int pivot) { public static int partitionOutsideIn(int a[], int lf, int rt, int pivot) { public static Pair partition2 Pivot (int a[], int lf, int rt, int pivotl, public static void HeapSortBottomUp (int a[], int n) { public static void HeapSortTopDown (int a[], int n) { public static void trickleDown (int a[], int lf, int rt) { public static void trickleUp(int a[], int rt) { int pivotr) { Computer Science 282 Programming Assignment #3 As always, add whatever is necessary so that the methods below behave correctly. Leave all variables, method names, and code fragments exactly as they appear. Only add code to make the methods work. The method names should make it clear what the method should do. Ask, preferably on Canvas, if you have any questions. A few reminders and rules (ask about these if you have questions!): Your sorts should work on 0-element arrays. Shift rather than swap during insertion and trickling. Be sure your various quicksort methods are making recursive calls to the proper quicksort method. Since there are multiple quicksorts it is easy to accidentally make the wrong recursive calls. The cutoff parameter in your quicksorts represents the smallest sized partition that will be recursively sorted, as described in week 10-lecture.pdf. For example, if cutoff = 10 then a partition with 10 elements will be recursively sorted while a partition of size 9 or less will not. Be sure you get this exactly right. It is easy to be off by 1. Also, don't get thrown off by the way the calculation is done in week 10-lecture.pdf. To be sure the stack does not overflow in your quicksorts write your recursive quicksort methods with a loop that: (1) selects the pivot, (2) partitions the array by calling a partition method, (3) makes the recursive call on the smaller partition(s), and (4) sets parameter values so that the loop simulates the second/third recursive call on the larger/largest partition. The code for QS_OutsideIn_randomPivot below should prove helpful but realize that it gets a little more complicated in the 2-pivot case. When partitioning, whenever an element is encountered that is the same as the pivot assume it is in the correct spot do not move it. // Used to return the two pivots in the 2-pivot partition class Pair { public int left, right; public } } Pair(int left, int right) { this. left = left; this.right right; // Class to hold all the sorts and their associated methods class ArraySorts { public static String myName() { public static void insertionSort(int a[], int n) { public static void QS_OutsideIn_randomPivot (int a[], int n, int cutoff) { QS_OutsideIn_randomPivot (a, 0, n - 1, cutoff); insertionSort (a, n); } private static void QS_OutsideIn_randomPivot (int a[], int lf, int rt, int cutoff) { } int pivot; while ((rt - lf + 1) >= cutoff) { pivot } } = pivot = partitionOutsideIn(a, lf, rt, pivot); lf + (int) (Math.random() * (rt lf + 1)); if ((pivot - lf) < (rt - pivot)) { } } else { QS_OutsideIn_randomPivot (a, lf, pivot-1, cutoff); lf = pivot+1; QS_OutsideIn_randomPivot(a, pivot+1, rt, cutoff); pivot -1; rt = public static void QS_LeftToRight_randomPivot (int a[], int n, int cutoff) { public static void QuickSort_2Pivot_Both Random (int a[], int n, int cutoff{ public static void QS_Outside In_lfPivot (int a[], int n, int cutoff) { public static void QS_LeftToRight_lfPivot (int a[], int n, int cutoff) { public static void AlmostQS_OutsideIn_randomPivot(int a[], int n, int cutoff) { QS_OutsideIn_randomPivot (a, 0, n - 1, cutoff); public static void AlmostQS_LeftToRight_randomPivot (int a[], int n, int cutoff) { public static void AlmostQuickSort_2Pivot_BothRandom (int a[], int n, int cutoff) { public static int partitionLeftToRight (int a[], int lf, int rt, int pivot) { public static void AlmostQS_LeftToRight_randomPivot(int a[], int n, int cutoff) { a[], int n, int cutoff) { public static void AlmostQuickSort_2Pivot_BothRandom(int public static int partitionLeftToRight(int a[], int lf, int rt, int pivot) { public static int partitionOutsideIn(int a[], int lf, int rt, int pivot) { public static Pair partition2 Pivot (int a[], int lf, int rt, int pivotl, public static void HeapSortBottomUp (int a[], int n) { public static void HeapSortTopDown (int a[], int n) { public static void trickleDown (int a[], int lf, int rt) { public static void trickleUp(int a[], int rt) { int pivotr) {
Expert Answer:
Answer rating: 100% (QA)
class Pair public int left right public Pairint left int right thisleft left thisright right Class t... 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...
-
Carol Harris, Ph.D, CPA, is a single taxpayer and she lives at 674 Yankee Street, Durham, NC 27409. Her Social Security number is 793-52-4335. Carol is an Associate Professor of Accounting at a local...
-
a. Determine IC and VCE for the network of Fig. 4.115. In Figure 4.115 b. Change β to 120 (50% increase), and determine the new values of lC and VCE for the network of Fig. 4.115. c....
-
ABC's taxable income for the year is $200,000 and CBA's taxable income for the year is $400,000. Compute the combined tax liability of the two corporations assuming the following: a. Amanda,...
-
In Exercises 7174, determine whether each statement is true or false. If the statement is false, make the necessary change(s) to produce a true statement. The ordered pair (2, 5) satisfies 3y - 2x =...
-
A contract is created to refurbish a luxury yacht: new color schemes, new furniture, new wall and floor coverings, new light fixtures, and window treatmentsthe whole works. Of course, it is not just...
-
Selected comparative financial statements of Bennington Company follow. Required 1. Compute each years current ratio. 2. Express the income statement data in common-size percents. 3. Express the...
-
Implement the Boolean function F(A.B.C.D) - (0,1,3,4,8,9,15) with a. a multiplexer b. a decoder Question 2 Draw the NAND gate representation of G A+ B'C' + DC. [10 marks] [5 marks] [5 marks]
-
Describe briefly- Multi-Programming Operating System.
-
How can advances in genomics, single-cell sequencing, and live-cell imaging technologies be leveraged to elucidate the spatiotemporal dynamics of meiotic events, meiotic gene expression networks, and...
-
The following financial information is available for Hero Sports Ltd.: Sales : $45,000 Costs : $25,000 Addition to retained earnings : $5,500 Dividends paid : $900 Interest expense : $1,450 Tax rate...
-
eBook Assume that the risk-free rate is 5% and the required return on the market is 13 %. What is the required rate of return on a stock with a beta of 27 Round your answer to two decimal places.
-
answer the following questions based on the article in complete sentences,...
-
Your company has arranged a revolving credit agreement for up to $78 million at an interest rate of 1.47 percent per quarter. The agreement also requires your company to maintain a compensating...
-
Write a paper fully describing your intended research methodology. Justify your choice(s) of methods, e.g., why qualitative or quantitative, why exploratory or experimental, etc. Describe what type...
-
If you want to solve a minimization problem by applying the geometric method to the dual problem, how many variables and problem constraints must be in the original problem?
-
During 2012, Palo Fiero purchases the following property for use in his manufacturing business: Palo uses the accelerated depreciation method under MACRS, if available, and does not make the election...
-
Mark owns his home and has a $250,000 mortgage related to his purchase of the residence. When his daughter went to college in the fall of 2012, he borrowed $20,000 through a home equity loan on his...
-
Carl Conch and Mary Duval are married and file a joint return. They live at 1234 Mallory Sq. Apt. 64, Key West, FL 33040. Carl works for the Key Lime Pie Company and Mary is a homemaker after losing...
-
Using the data from Table 2, construct a \(95 \%\) confidence interval estimate of the mean difference, \(\mu_{d}\). By Hand Approach Step 1 Compute the differenced data. Because the sample size is...
-
Problem Decide whether the sampling method is independent or dependent. Then determine whether the response variable is qualitative or quantitative. (a) Joliet Junior College decided to implement a...
-
In the Spacelab Life Sciences 2 payload, 14 male rats were sent to space. Upon their return, the red blood cell mass (in milliliters) of the rats was determined. A control group of 14 male rats was...
Study smarter with the SolutionInn App