Write a function to implement meansort

Assignment Help Computer Engineering

Reference no: EM131847652

Problem

A different approach to the selection of pivot is to take the mean (average) of meansort all the keys in the list as the pivot. The resulting algorithm is called meansort.

(a) Write a function to implement meansort. The partition function must be modified, since the mean of the keys is not necessarily one of the keys in the list. On the first pass, the pivot can be chosen any way you wish. As the keys are then partitioned, running sums and counts are kept for the two sublists, and thereby the means (which will be the new pivots) of the sublists can be calculated without making any extra passes through the list.

(b) In meansort, the relative sizes of the keys determine how nearly equal the sublists will be after partitioning; the initial order of the keys is of no importance, except for counting the number of swaps that will take place. How bad can the worst case for meansort be in terms of the relative sizes of the two sublists? Find a set of n integers that will produce the worst case for meansort.

Reference no: EM131847652

Questions Cloud

How can earn profit with successful campaigns : Mary is not sure if her customers would appreciate her selling their personal information and how it might affect her business.

Why isnt aspirin recommended for children : Why isnt aspirin recommended for children? Is it relation to Reye's or lack of liver metabolization of certain drugs?

What is the etiological agent of moniliasis : What is the etiological agent of moniliasis and what is the other name for the disease? Why is monilia also common in healthy newborns?

What is the use of this drug to the patient : The nurse explains that shelooked in the package insert and found nothing about using the drug intravenously. What is the use of this drug to the patient?

Write a function to implement meansort : Write a function to implement meansort. The partition function must be modified, since the mean of the keys is not necessarily one of the keys in the list.

How much extra computation will be done : How much extra computation will be done? For n = 7, find an ordering of the keys 1, 2, ... , 7 that will force the algorithm into its worst case.

Prepare a report summarizing crm systems : Create a report summarizing CRM systems and detail how such a system can directly influence Cold Cream's revenues.

Compare the different processes of pharmacokinetics : Compare the different processes of pharmacokinetics and the factors that influence each one. Briefly explain pharmacodynamics and provide an example

What are the manifestations of hyperglycemia : In the report, the PACU nurse instructs that the patient must be monitored for hyperglycemia. What are the manifestations of hyperglycemia?

User Account

All Pages