Find a sorting method for four keys

Assignment Help Computer Engineering

Reference no: EM131847632

Problem

1. Draw the comparison trees for (a) insertion sort and (b) selection sort applied to four objects.

2. (a) Find a sorting method for four keys that is optimal in the sense of doing the smallest possible number of key comparisons in its worst case.

(b) Find how many comparisons your algorithm does in the average case (applied to four keys). Modify your algorithm to make it come as close as possible to achieving the lower bound of lg 4! ≈ 4.585 key comparisons. Why is it impossible to achieve this lower bound?

Reference no: EM131847632

Questions Cloud

Write a program to perform a linked distribution sort : Write a program to perform a linked distribution sort, as follows. Take the keys to be pseudorandom numbers between 0 and 1, as linked distribution.

Developing and approving a new drug in the united states : Briefly describe the phases involved in each step of developing and approving a new drug in the United States.

Create a document detailing the features of wireless network : Securing a home wireless network is invaluable and allows you to enable security features that can make it difficult for uninvited guests to connect.

Contrasts the prototype drugs labetalol : Construct a table that compares and contrasts the prototype drugs labetalol, phenotalamine, doxozasin, propranolol, and atenolol. what conditions

Find a sorting method for four keys : Find a sorting method for four keys that is optimal in the sense of doing the smallest possible number of key comparisons in its worst case.

Prototype drugs labeltalol and propranolol : Each group is assigned one of the prototype drugs labeltalol and propranolol. Create a case stusy for a patient who will be given the the assigned drugs.

Create a product using a gps or gis : Create a product, using a GPS or GIS, that is not currently in the market today that you will present at the fourth annual PennVention.

How many comparisons of keys will be done by count sort : Determine how many comparisons of keys will be done by count sort. Is it a better algorithm than selection sort?

How could local businesses and citizens benefit from network : You are responsible for deploying a CitySense network around your city. What goals would you have for the system besides monitoring urban weather and pollution?

User Account

All Pages