If the conditional at line 14 of our quickSortInPlace implementation of Code Fragment 12.6 were changed to
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: 33% (12 reviews)
If left right immediately after the inner loops complete i...View the full answer
Answered By
Lamya S
Highly creative, resourceful and dedicated High School Teacher with a good fluency in English (IELTS- 7.5 band scorer) and an excellent record of successful classroom presentations.
I have more than 2 years experience in tutoring students especially by using my note making strategies.
Especially adept at teaching methods of business functions and management through a positive, and flexible teaching style with the willingness to work beyond the call of duty.
Committed to ongoing professional development and spreading the knowledge within myself to the blooming ones to make them fly with a colorful wing of future.
I do always believe that more than being a teacher who teaches students subjects,...i rather want to be a teacher who wants to teach students how to love learning..
Subjects i handle :
Business studies
Management studies
Operations Management
Organisational Behaviour
Change Management
Research Methodology
Strategy Management
Economics
Human Resource Management
Performance Management
Training
International Business
Business Ethics
Business Communication
Things you can expect from me :
- A clear cut answer
- A detailed conceptual way of explanation
- Simplified answer form of complex topics
- Diagrams and examples filled answers
4.90+
46+ Reviews
54+ 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
-
If the outermost while loop of our implementation of quickSortInPlace (line 9 of Code Fragment 12.6) were changed to use condition left < right, instead of condition left /** Sort the subarray S[a.b]...
-
Is our linked-list-based implementation of merge-sort (Code Fragment 12.3) stable? Explain why or why not. /** Merge contents of sorted queues S1 and S2 into empty queue S. */ public static void...
-
The following pseudocode is a correct implementation of the producer/consumer problem with a bounded buffer: Labels p1, p2, p3 and c1, c2, c3 refer to the lines of code shown above (p2 and c2 each...
-
Division A of ABC, Inc. produces part TZ20 that is used by Division B in the manufacture of product 100BD.Below is a summary of the manufacturing costs of the TZ20 part: Direct Labour $8.00 per unit...
-
GlaxoSmithKline Plc. (GSK) is a global pharmaceutical and consumer health-related products company located in the United Kingdom. The company prepares its financial statements in accordance with...
-
Tom Smithfield is valuing the stock of a food - processing business. He feels confident explicitly projecting earnings and dividends to three years (to t = 3). Other information and estimates are as...
-
A study collected data comparing treatments for kidney stones. Two of the treatments studied were open surgery and percutaneous nephrolithotomy. Treatment was deemed "successful" if, after three...
-
The accountant at Fighting Kites has always prepared a budget that is calculated using only one estimated volume of sales. He has asked you to help him set up a spreadsheet that can be used for...
-
Identify the type of fund in which each activity is recorded: 1 ) The city receives a grant from the federal government to institute a meal delivery program for senior citizens. 2 ) To remedy a...
-
Please evaluate whether the IBMs acquisition of Red Hat is a good deal or a bad deal by considering the short- and long-term debt taken by IBM to fund the acquisition of Red Hat alongside projected...
-
Following our analysis of randomized quick-sort in Section 12.2.1, show that the probability that a given input element x belongs to more than 2logn subproblems in size group i is at most 1/n 2 .
-
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...
-
In Exercises 1 through 8, find the slope (if defined) of the line that passes through the given pair of points. (2, 6) and (2, 4)
-
In the source routing example, the address received by B is not reversible and does not help B know how to reach A. Propose a modification to the delivery mechanism that does allow for reversibility....
-
For the network given in Figure 3.51, show how the link-state algorithm builds the routing table for node D. Figure 3.51) D A 8 3 B 2 2 1 E 6 F LL
-
Suppose that when a TCP segment is sent more than once, we take SampleRTT to be the time between the most recent transmission and the ACK, as in Figure 5.10(b). Assume, for definiteness, that TimeOut...
-
What kind of problems can arise when two hosts on the same Ethernet share the same hardware address? Describe what happens and why that behavior is a problem.
-
The existing Internet depends in many respects on participants being good network citizenscooperating above and beyond adherence to standard protocols. (a) In the PIM-SM scheme, who determines when...
-
The variable where the effect is measured in an experimental design is called the ____.
-
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....
-
Show the comparisons the naive string matcher makes for the pattern P = 0001 in the text T = 000010001010001.
-
Let y i denote the concatenation of string?y?with itself?i?times. For example,?(ab) 3 =?ababab. We say that a string?x???? * has?repetition factor?r?if?x?=?y r for some string?y???? * and some?r > 0....
-
Give an efficient algorithm to convert a given -bit (binary) integer to a decimal representation. Argue that if multiplication or division of integers whose length is at most takes time M(), then we...
-
As of June 30, Year 1, the bank statement showed an ending balance of $16,878. The unadjusted Cash account balance was $15,239. The following information is available: 1. Deposit in transit, $2,190....
-
Superior Company provided the following data for the year ended December 31 (all raw materials are used in production as direct materials): Selling expenses Purchases of raw materials Direct labor...
-
Marin Company produces two software products (Cloud-X and Cloud-Y) in two separate departments (A and B). These products are highly regarded network maintenance programs. Cloud-X is used for small...
Study smarter with the SolutionInn App