We can modify Insertion Sort to insert a pair of elements at a time, instead of...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
We can modify Insertion Sort to insert a pair of elements at a time, instead of only one element: Find the larger element of the pair and put it into its proper location in the sorted array using linear search (as in standard insertion sort). Then, starting from where the larger element ended up, put the smaller element into its proper location again using linear search. (a) Write the pseudo code, using a sentinel, for this algorithm. You may assume that the size of the array is even. (b) Assume the size of the array n = 4. i. What is the best-case number of comparisons? Just state the number and show your input. Otherwise, no justification needed. ii. What is the worst-case number of comparisons? Just state the number and show your input. Otherwise, no justification needed. iii. What is the average-case number of comparisons? Justify. HINT: There are 24 pos- sible orderings, which is a lot. The calculation is more manageable if you realize that the first pair of elements essentially defines the whole ordering. (c) Calculate the average case number of comparisons for general n, where n is even. Show your work. (d) How does the average case number of comparisons compare with the average case of standard insertion sort? We can modify Insertion Sort to insert a pair of elements at a time, instead of only one element: Find the larger element of the pair and put it into its proper location in the sorted array using linear search (as in standard insertion sort). Then, starting from where the larger element ended up, put the smaller element into its proper location again using linear search. (a) Write the pseudo code, using a sentinel, for this algorithm. You may assume that the size of the array is even. (b) Assume the size of the array n = 4. i. What is the best-case number of comparisons? Just state the number and show your input. Otherwise, no justification needed. ii. What is the worst-case number of comparisons? Just state the number and show your input. Otherwise, no justification needed. iii. What is the average-case number of comparisons? Justify. HINT: There are 24 pos- sible orderings, which is a lot. The calculation is more manageable if you realize that the first pair of elements essentially defines the whole ordering. (c) Calculate the average case number of comparisons for general n, where n is even. Show your work. (d) How does the average case number of comparisons compare with the average case of standard insertion sort?
Expert Answer:
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these programming questions
-
Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...
-
CANMNMM January of this year. (a) Each item will be held in a record. Describe all the data structures that must refer to these records to implement the required functionality. Describe all the...
-
Cover time. Write a program that estimates the time required for the random surfer to visit every page at least once, starting from a random page.
-
In getting ready for a telephone interview for a new job, what are the three or four things for which you most want to be prepared? If you are getting ready to interview someone else for a job, what...
-
1. What category of corporation is Pharma, and what are the options in terms of structure and raising capital? 2. Is Pharma eligible for S corporation status? If one of the shareholders objected,...
-
CMS is a claims processing company in Mobile, Alabama. Chastity Jones, a black woman, completed an online employment application for a customer service position with CMS. Jones interviewed with a...
-
The income statement of Rodriquez Company is shown below. Additional information: 1. Accounts receivable decreased $310,000 during the year. 2. Prepaid expenses increased $170,000 during the year. 3....
-
Peanut Company acquired 80 percent of Snoopy Company's outstanding common stock for $276,800 on January 1, 20X8, when the book value of Snoopy's net assets was equal to $346,000. Peanut uses the...
-
Hypothesis Testing for the Population Proportion Use a cell reference or a single formula where appropriate in order to receive full credit. Do not copy and paste values or type values, as you will...
-
MM Company's current stock price is Tk. 237 and its last dividend was Tk. 11.5 per share. The company's required rate of return is 12.5 %. Dividend payout ratio of this company is 21% and the return...
-
The difference of specific heats for an ideal gas, \(c_{p, m}-c_{v, m}=\Re\). Evaluate the difference in specific heats for gases obeying (1) the van der Waals and (2) the Dieterici equations of...
-
A single fair die is rolled. Let the event \(A\) be the face showing is even. Let the event \(B\) be the face showing is divisible by 3 . (a) List out the sample space of the experiment. (b) List the...
-
Let \(X\) be a random variable having probability density function \[ f(x)=2 x \text { for } \quad 0 \quad x \quad 1 \] (a) Find \(P\left(\begin{array}{ll}X \quad 75\end{array} ight)\). (b) Find...
-
Let \(X\) have the uniform distribution. (a) Find \(\mathrm{E}[X]\). (b) Find \(\operatorname{Var}[X]\). (c) Find \(P\left(\begin{array}{ll}X \quad 25\end{array} ight)\). (d) Find \(P(33
-
Let \(X\) have a \(\operatorname{beta}(12\) 4) distribution. (a) Find \(\mathrm{E}[X]\). (b) Find \(\operatorname{Var}[X]\).
-
Write a paper on the topic Family Matters: Family Environment and Delinquency
-
On April 29, 2015, Auk Corporation acquires 100% of the outstanding stock of Amazon Corporation (E & P of $750,000) for $1.2 million. Amazon has assets with a fair market value of $1.4 million (basis...
-
We can apply the iteration operator ? used in the lg ? function to any monotonically increasing function f (n) over the reals. For a given constant c ? ?, we define the iterated function f * c by...
-
A group of n Ghostbusters is battling n ghosts. Each Ghostbuster carries a proton pack, which shoots a stream at a ghost, eradicating it. A stream goes in a straight line and terminates when it hits...
-
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....
-
List all of the factors you can think of that people use when deciding where to shop for clothes.
-
List the most important three factors for you personally when deciding where to shop for clothes.
-
Intel has dominated the computer chip industry. Beginning with the iconic advertising campaign Intel Inside, the company has created a large market for powerful processors. This has allowed Intel to...
Study smarter with the SolutionInn App