Develop a new partitioning function

Assignment Help Computer Engineering

Reference no: EM132117902

Quick sort is to partition the array around one element and then sort each part recursively. We pick up one element as the pivot and then move all elements less than the pivot to the left, and all elements greater than the pivot to the right.

We then recurse on the left and right parts. In a case of an array that contains many duplicates, quicksort will recurse on all duplicates of the pivot element.

You are to develop a new partitioning function that works better on arrays with duplicates. The idea is to partition the array into elements less than the pivot, equal to the pivot and greater than the pivot. 2

(a) Write a pseudocode for your suggested partitioning algorithm. Make sure your algorithm is in-place (i.e., do not use more than a constant amount of extra space).

(b) Using your suggested partitioning algorithm in part (a), come up with a sorting algorithm. Analyze the worst-case running time of your algorithm.

Reference no: EM132117902

Questions Cloud

Compute your bank balance for the given time periods : Interest on your bank balance: Suppose your bank account has a balance today of $100. Consider the following time periods: t = 0, t = 1, t = 2, t = 12, t = 24.

What is the required return on portfolio : The risk-free rate is 6.4 percent and the market risk premium is 5 percent. Assume that required returns are based on the CAPM. Your $1 million portfolio

List relevant quantitative data : List relevant qualitative data: Evidence related to or based on the quality or character of something - List relevant quantitative data

How sensitive is the calculation to the rate of return : Stock returns and your retirement account: Suppose your retirement account has a balance today of $25,000 and you are 20 years old.

Develop a new partitioning function : Using your suggested partitioning algorithm in part (a), come up with a sorting algorithm. Analyze the worst-case running time of your algorithm.

Assuming an nominal interest rate : What was the effective price you received for the motorcycle assuming an nominal interest rate of 8.5%? Show your answer to the nearest $.01.

Label the value of per capita gdp on the graph : The ratio scale: Plot the following scenarios for per capita GDP on a ratio scale. Assume that per capita GDP in the year 2015 is equal to $10,000.

Which argument do you find more convincing : The costs of economic growth? In addition to the benefits of economic growth, there are also potentially costs. What are some of these costs?

What is the price of a 15-year : What is the price of a 15-year, zero coupon bond paying $1,000 at maturity, assuming semiannual compounding, if the YTM is: a. 6 percent? b. 8 percent? c. 10 pe

User Account

All Pages