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?

Reviews

Write a Review

Computer Engineering Questions & Answers

  Mathematics in computing

Binary search tree, and postorder and preorder traversal Determine the shortest path in Graph

  Ict governance

ICT is defined as the term of Information and communication technologies, it is diverse set of technical tools and resources used by the government agencies to communicate and produce, circulate, store, and manage all information.

  Implementation of memory management

Assignment covers the following eight topics and explore the implementation of memory management, processes and threads.

  Realize business and organizational data storage

Realize business and organizational data storage and fast access times are much more important than they have ever been. Compare and contrast magnetic tapes, magnetic disks, optical discs

  What is the protocol overhead

What are the advantages of using a compiled language over an interpreted one? Under what circumstances would you select to use an interpreted language?

  Implementation of memory management

Paper describes about memory management. How memory is used in executing programs and its critical support for applications.

  Define open and closed loop control systems

Define open and closed loop cotrol systems.Explain difference between time varying and time invariant control system wth suitable example.

  Prepare a proposal to deploy windows server

Prepare a proposal to deploy Windows Server onto an existing network based on the provided scenario.

  Security policy document project

Analyze security requirements and develop a security policy

  Write a procedure that produces independent stack objects

Write a procedure (make-stack) that produces independent stack objects, using a message-passing style, e.g.

  Define a suitable functional unit

Define a suitable functional unit for a comparative study between two different types of paint.

  Calculate yield to maturity and bond prices

Calculate yield to maturity (YTM) and bond prices

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd