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...
-
Solve for x. 25x-7= 8 x =
-
Water flows through two sections of the vertical pipe shown in Fig. P8.95. The bellows connection cannot support any force in the vertical direction. The 0.4-ft-diameter pipe weights \(0.2...
-
Maria Ochoa receives two new credit cards on May 1. She had solicited one of them from Midtown Department Store, and the other arrived unsolicited from High-Flying Airlines. During the month of May,...
-
Bartholemew Incorporated uses a job-order costing system and its total manufacturing overhead applied always equals its total manufacturing overhead. In February the company completed job G43C that...
-
Create a hotel and include the following below . Name of business and logo/ emblem Who are the entrepreneurs? Primary activities, industry. Description of product / services. Background, where does...
-
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...
-
Dufner Co. issued 15-year bonds one year ago at a coupon rate of 4.8 percent. The bonds make semiannual payments. If the YTM on these bonds is 5.3 percent, what is the current dollar price assuming a...
-
With whom might we have downward communication, upward communication, and lateral communication in the workplace? What are the differences among these?
-
How is libel different from slander?
-
What makes listening active listening? Why is active listening valuable?
-
What makes communication nonverbal?
-
On YouTube, watch clips of three presentations by Steve Jobs. What similarities do you see among them? What are some of his techniques you could use in a job you hope to have? Which ones do you think...
-
Balance the chemical equation for each reaction. C 7 H 6 O 2 + O 2 H 2 O + CO 2
-
Critical reading SAT scores are distributed as N(500, 100). a. Find the SAT score at the 75th percentile. b. Find the SAT score at the 25th percentile. c. Find the interquartile range for SAT scores....
-
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...
-
A 10-kg green ball and a 2-kg purple ball collide. Before the collision, the green ball's velocity is +2.0 m/s, and the purple ball's is -4.0 m/s. After the collision, the purple ball's velocity is...
-
what ways does organizational culture, encompassing values, norms, and leadership styles, influence team cohesion, morale, and productivity, and how can organizations cultivate a culture that...
-
A large helium filled balloon is used as the center piece for an advertising display. The balloon alone has a mass of 225 kg and it is filled with helium gas until its volume is 326 m.
Study smarter with the SolutionInn App