Algorithm for sorting an array segment

Assignment Help Business Management
Reference no: EM131912150

Consider the following algorithm for sorting an array segment A[0..n-1]. In the first step the algorithm performs the bubble-up operation on the range [0..n-1] and it places the smallest item on position 0. In the second step it performs the bubble-down operation on the range [1..n-1] and it places the largest item on position n-1. In the third step it performs bubble-up operation on the range [1..n-2] and it places the second smallest item on position 1. In the fourth step it performs the bubble-down operation on the range [2..n-2] and it places the second largest item on position n-2. The algorithm continues alternating bubble-up and bubble-down operations until the range consists of a single field.

(i) What is the number of swap operations performed in the worse case?

(ii) What is the average number of swap operations performed by this algorithm? Provide justifications to your answers.

Reference no: EM131912150

Questions Cloud

Reflect on the analysis of the sin of suicide : Reflect on the analysis of the sin of suicide and thus, euthanasia. Do you agree? Why or why not? 300 words.
Access management services : Today, several security services are increasingly provided as common security services. These include audit and monitoring services, authentication services
Comparing keys and operating : Let T be the decision tree of a sorting algorithm based on comparing keys and operating on a list containing n different keys. Show that the height
Was the original source of information reputable : Was the original source of information reputable? Why/Why not? Please provide evidence from reputable sources to support your response for each article/item.
Algorithm for sorting an array segment : Consider the following algorithm for sorting an array segment A[0..n-1]. In the first step the algorithm performs the bubble-up operation on the range
Construct the list of values for some initial segment : CSD3203 – History and Philosophy of Computing The Halting Problem and Uncomputability - Who proved that the halting problem was impossible to solve, and when
Describe an algorithm that makes use of the sorted : A sorted list of n strings is given. Describe an algorithm that makes use of the sorted order and determines whether a given string x is a member of this list.
Digital devices from paul douglas peters : Assume a warrant was granted to search and seize digital devices from Paul Douglas Peters' residence.
Find a formula expressing the sum of degrees : Find a formula expressing the sum of degrees of all nodes of a tree in terms of the number of its nodes. Prove your formula by structural induction.

Reviews

Write a Review

Business Management Questions & Answers

  Evaluate five strategic business units cost or profit center

Should Hamilton-Jones evaluate the five strategic business units as cost or profit centers? Why? How should the administrative support areas be evaluated?

  Describe the relationship between a corporation commont

1. Describe the relationship between a corporation's common stockholders, its board of directors, and its chief executive officer (CEO).

  Social and ethical consequences of the businesses

What are the social and ethical consequences of the businesses related to the excessive production of food to the consumer?

  Develop a list of possible metrics

Many Western firms see their futures in the growing populations of developing countries.- Develop a list of possible metrics that firms might use to measure their success in these new developing markets.

  Type of hydrocarbons

1. Point out how and what type of hydrocarbons may be formed in nature without necessarily being influenced by anthropogenic activities.

  Calculate the price of a product produced

A manager wants to calculate the price of a product produced by the firm she works for. Recent calculations show that the elasticity value of the product.

  Respective company performance

Analyze how each leadership style might affect the respective company's performance and alignment to values. Discuss which leadership style you are most aligned to.

  Journal entry to record the issuance of the bonds

Prepare the journal entry to record depletion expense. Assume that the 100,000 tons of ore were mined, but only 80,000 units were sold. How are the costs applicable to the 20,000 unsold units reported?

  Create a presentation that describes what stuxnet worm is

Research the Stuxnet Worm. Create a multimedia presentation that describes what the Stuxnet worm is, how it applies to SCADA, what components, if any, are affected by the worm, and other details you feel are necessary.

  Problem regarding the labor relations

This assignment is intended to enable you to make a personal connection to our study of labor history.  Each of us adults has an employment history.  In addition, our family's employment history can personalize and enrich class discussion of the e..

  Rapid transformation of us health care industry

Introduction: With the rapid transformation of the U.S. health care industry, today's HIM (including health care managers) professional requires an advanced level of skill sets and training.

  Determining the country analysis matrix

Compare the US and one other country. Collect the economic data outlined in the Country Analysis Matrix that is attached. Conduct research through a minimum of three readings from The Economist. Use citations for the three articles from The Econom..

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