Is our linked-list-based implementation of merge-sort (Code Fragment 12.3) stable? Explain why or why not. /** Merge
Question:
Transcribed Image Text:
/** Merge contents of sorted queues S1 and S2 into empty queue S. */ public static
/** Merge contents of sorted queues S1 and S2 into empty queue S. */ public static void merge(Queue S1, Queue S2, Queue S, Comparator comp) { 3 while (!S1.isEmpty() && !S2.isEmpty()) { if (comp.compare(S1.first(), S2.first()) < 0) S.enqueue(S1.dequeue( )); else 4 // take next element from S1 6. // take next element from S2 S.enqueue(S2.dequeue( )); } while (!S1.isEmpty()) S.enqueue(S1.dequeue()); while (!S2.isEmpty()) S.enqueue(S2.dequeue( )); } 10 // move any elements that remain in S1 11 12 // move any elements that remain in S2 13 14 15 /** Merge-sort contents of queue. */ public static void mergeSort(Queue S, Comparator comp) { int n = S.size(); if (n < 2) return; // divide Queue S1 = new LinkedQueue<>(); Queue S2 = new LinkedQueue<>(); while (S1.size() < n/2) S1.enqueue(S.dequeue()); while (!S.isEmpty()) S2.enqueue(S.dequeue( )); // conquer (with recursion) mergeSort(S1, comp); mergeSort(S2, comp); // merge results merge(S1, S2, S, comp); } 16 17 18 // queue is trivially sorted 19 20 // (or any queue implementation) 21 22 23 // move the first n/2 elements to S1 24 25 // move remaining elements to S2 26 27 // sort first half // sort second half 28 29 30 // merge sorted halves back into original 31 32
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 84% (13 reviews)
It is not stable Given equ...View the full answer
Answered By
YOGENDRA NAILWAL
As I'm a Ph.D. student, so I'm more focussed on my chemistry laboratory. I have qualified two national level exams viz, GATE, and NET JRF (Rank 68). So I'm highly qualified in chemistry subject. Also, I have two years of teaching experience in this subject, which includes college teacher as well as a personal tutor. I can assure you if you hire me on this particular subject, you are never going to regret it.
Best Regards.
5.00+
1+ 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
-
Is our array-based implementation of merge-sort given in Section 12.1.2 stable? Explain why or why not.
-
Consider lines 3133 of Code Fragment 10.8 in our implementation of the class ChainHashMap. We use the difference in the size of a secondary bucket before and after a call to bucket.remove(k) to...
-
Consider the implementation of CircularlyLinkedList.addFirst, in Code Fragment 3.16. The else body at lines 39 and 40 of that method relies on a locally declared variable, newest. Redesign that...
-
Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin's value is an integer. 2. Suppose that the available coins are in the denominations that are...
-
The following income statement items appeared on the adjusted trial balance of Schembri Manufacturing Corporation for the year ended December 31, 2018 ($ in thousands): sales revenue, $15,300; cost...
-
1. Could you argue that the other items, such as information regarding sexual harassment and discrimination complaints against Lee, might help a shareholder determine if the company was well run? 2....
-
Earnings per share is not computed for a. Net income b. Comprehensive income c. Discontinued operations d. Extraordinary items
-
The post-closing trial balances of two proprietorships on January 1, 2010, are presented below. John and Calvin decide to form a partnership, John-Calvin Company, with the following agreed upon...
-
Shortly after taking over for the previous chef at Magnolia's, Chef Hendrix theorized their restaurant's current menu prices had not been changed for some time. After a quick calculation, he was...
-
UB is examining its capital structure with the intent of arriving at an optimal debt ratio. It currently has no debt and has a beta of 1.5. The riskless interest rate is 9%. Your research indicates...
-
Suppose we are given two n-element sorted sequences A and B each with distinct elements, but potentially some elements that are in both sequences. Describe an O(n)-time method for computing a...
-
Give a complete justification of Proposition 12.1.
-
Weighted-average method, assigning costs. Bio Doc Corporation is a biotech company based in Milpitas. It makes a cancer-treatment drug in a single processing department. Direct materials are added at...
-
In this activity, you will download two tables of data from the Homeland Infrastructure Foundation-Level Data (HIFLD) website and one table of data from the American Community Survey (ACS)....
-
Threats from HR Perspective Are there stricter federal, state, and local employment laws? Are any other companies in the area are hiring for similar positions and skills? Is there any market...
-
Imagine a scenario where you need to follow up with a potential investor after an initial meeting. How would you structure a follow-up letter to express gratitude, reiterate key points, and encourage...
-
In July 2021, Vio Bank was offering 0.61% interest on its money market account. Assuming interest is reinvested daily, find the associated exponential model for the value of a $3,000 deposit after t...
-
Discuss two different types of investments that can be considered a Money Market Fund and briefly discuss their important characteristics, being sure to identify the meanings of those characteristics...
-
let U = {a, b, c, d, e, f, g, h, i, j, k} A = {a, c, d, f, g, i} B = {b, c, d, f, g} C = {a, b, f, i, j} Determine the following. B C
-
Suppose the S&P 500 futures price is 1000, = 30%, r = 5%, = 5%, T = 1, and n = 3. a. What are the prices of European calls and puts for K = $1000? Why do you find the prices to be equal? b. What...
-
Prove that if a | b and b | c, then a | c.
-
How many steps would you expect POLLARD-RHO to require to discover a factor of the form p e , where p is prime and e > 1?
-
Prove that if x is a nontrivial square root of 1, modulo n, then gcd (x 1, n) and gcd (x + 1, n) are both nontrivial divisors of n.
-
Time Value of Money calculations are a great way to figure out how much payments will be on loans or how much we need to save over time to achieve our financial goals. The calculation always uses the...
-
Dawson Toys, Limited, produces a toy called the Maze. The company has recently created a standard cost system to help control costs and has established the following standards for the Maze toy:...
-
Employer sponsored health care coverage create situation in which health insurers face high moral hazard. a. Graphically describe how health insurance creates this moral hazard. In your answer,...
Study smarter with the SolutionInn App