If the outermost while loop of our implementation of quickSortInPlace (line 9 of Code Fragment 12.6) were
Question:
Transcribed Image Text:
/** Sort the subarray S[a.b] inclusive. */ private static
/** Sort the subarray S[a.b] inclusive. */ private static void quickSortInPlace(K[] S, Comparator comp, int a, int b) { 3 // subarray is trivially sorted if (a >= b) return; int left = a; 4 5 int right = b-1; K pivot = S[b]; K temp; while (left <= right) { // scan until reaching value equal or larger than pivot (or right marker) while (left <= right && comp.compare(S[left], pivot) < 0) left++; // scan until reaching value equal or smaller than pivot (or left marker) while (left <= right && comp.compare(S[right], pivot) > 0) right--; if (left <= right) { // so swap values and shrink range temp = S[left]; S[left] = S[right]; S[right] = temp; left++; right--; %3D // temp object used for swapping 10 11 12 13 // indices did not strictly cross 14 15 16 17 18 } // put pivot into its final place (currently marked by left index) temp = S[left]; S[left] = S[b]; S[b] = temp; // make recursive calls quickSortInPlace(S, comp, a, left – 1); quickSortInPlace(S, comp, left + 1, b); 19 20 21 22 23 24 25
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 75% (8 reviews)
Within the loop just after swapping two elements left is incremented and right is decremented ...View the full answer
Answered By
Saurabh Kumar
I just love sharing my shortcuts and techniques with students to approach math problems. It gives me immense satisfaction when they are happy with my solution.
0.00
0 Reviews
10+ Question Solved
Related Book For
Data Structures and Algorithms in Java
ISBN: 978-1118771334
6th edition
Authors: Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
Question Posted:
Students also viewed these Computer science questions
-
Our implementation of the treeSearch utility, from Code Fragment 11.3, relies on recursion. For a large unbalanced tree, it is possible that Javas call stack will reach its limit due to the recursive...
-
In our implementation of the scale function (page 25), the body of the loop executes the command data[j] *= factor. We have discussed that numeric types are immutable, and that use of the *= operator...
-
The performance of a snooping cache-coherent multiprocessor depends on many detailed implementation issues that determine how quickly a cache responds with data in an exclusive or M state block. In...
-
For this project, you must select an employer organization and research the organizations employee benefits package (plan). After you research the organizations employee benefits package, collect...
-
The following events occurred during 2018 for various audit clients of your firm. Consider each event to be independent and the effect of each event to be material. 1. A manufacturing company...
-
1. CPA QUESTION: Which of the following requirements must be met to create a bailment? I. Delivery of personal property to the intended bailee II. Possession by the intended bailee III. An absolute...
-
Selected account balances for Jills Java at the end of the month are listed below in random order: Identify or compute the following amounts for Jills Java: a. Total current assets b. Total current...
-
Yeager Company pays John Kerr a salary as an employee and also fees for work he does as an independent contractor. Does this violate IRS rules?
-
Exhibit 2 Balance Sheets at December 31, 1993-1995, and March 31, 1996 (thousands of dollars) 1st Quarter 1993 1994 1995 1996 Cash $ 43 $ 52 $ 56 $ 53 Accounts receivable, net 306 411 606 583...
-
Sawyers, a local bakery, is worried about increased costsparticularly energy. Last years records provide a fairly good estimate of the parameters for this year. Judy Sawyer, the owner, does not...
-
If the conditional at line 14 of our quickSortInPlace implementation of Code Fragment 12.6 were changed to use condition left < right, instead of condition left /** Sort the subarray S[a.b]...
-
Suppose the method quickSortInPlace is executed on a sequence with duplicate elements. Prove that the algorithm still correctly sorts the input sequence. What happens in the partition step when there...
-
For some regions, both the washer and shell methods work well for the solid generated by revolving the region about the coordinate axes, but this is not always the case. When a region is revolved...
-
A painting with a mass of 21 kg is suspended by two wires from hooks on a ceiling. if the wires have lengths of 21 cm and 30 cm and the distance between the hooks is 35 cm , find the tension in each...
-
answer this question in Java and only if you are fully confident of the answer. The code should work without any errors. These are not stocks, but transactions that have occurred. Cashback value can...
-
Question 1 (20P) When the single-index model is used, the variance of a security's return is expressed as: o = o +0 Derive the equation above for the variance security's return by using the...
-
Frank gave Betty real estate with a basis of $100,000 and marketable securities with a basis of $20,000. In exchange, Betty gave Frank real estate with a basis of $240,000 and worth $300,000. The...
-
3. Consider the stratified fluid depicted below which is being sheared between two infinite parallel plates. If the upper plate is constrained to move with velocity U, the lower plate is fixed, and...
-
Use Fig. During a session of the U.S. Senate, three bills were voted on. The votes of six senators are shown. Determine in which region of the figure each senator should be placed. The set labeled...
-
You continue to work in the corporate office for a nationwide convenience store franchise that operates nearly 10,000 stores. The per- store daily customer count (i.e., the mean number of customers...
-
Give efficient algorithms for the operations of dividing a -bit integer by a shorter integer and of taking the remainder of a -bit integer when divided by a shorter integer. Your algorithms should...
-
Show that the gcd operator is associative. That is, prove that for all integers a, b, and c, gcd (a, gcd (b, c)) = gcd (gcd (a, b), c),
-
Prove that n 1 , n 2 , n 3 , and n 4 are pairwise relatively prime if and only if gcd(n 1 n 2 , n 3 n 4 ) = gcd (n 1 n 3 , n 2 n 4 ) = 1. More generally, show that n 1 , n 2 , . . . ,n k are pairwise...
-
Find 7e dx + C
-
Explain the differences between containerization and virtualization. What are the benefits and limitations of each approach in terms of resource isolation and scalability ?
-
Discuss common techniques used to optimize operating system performance. How do profiling, caching, and load balancing play a role in improving system efficiency ?
Study smarter with the SolutionInn App