What is the running time of quicksort

Assignment Help Data Structure & Algorithms
Reference no: EM131077386

BUILD-MAX-HEAP(A)

1. A. heap-size = A .length

2. for i = [A.length/2J downto 1

3. MAX-HEAPIFY (A, i)

Shows an example of the action of BUILD-MAX-HEAP.

Problem 1. Why do we want the loop index i in line 2 of BUILD-MAX-HEAP to decrease from [A.length/2] to 1 rather than increase from 1 to [A. length/2]?

Problem 2.

The operation HEAP-DELETE (A, i) deletes the item in node i from heap A. Give an implementation of HEAP-DELETE that runs in 0(lg n) time for an n-element max-heap.

Problem 3.

What is the running time of QUICKSORT when all elements of array A have the same value?

Problem 4.

Banks often record transactions on an account in order of the times of the transac-tions, but many people like to receive their bank statements with checks listed in order by check number. People usually write checks in order by check number, and merchants usually cash them with reasonable dispatch. The problem of converting time-of-transaction ordering to check-number ordering is therefore the problem of sorting almost-sorted input. Argue that the procedure INSERTION-SORT would tend to beat the procedure QUICKSORT on this problem.

Problem 5.

Why do we analyze the expected running time of a randomized algorithm and not its worst-case running time?

Problem 6.

What is the smallest possible depth of a leaf in a decision tree for a comparison sort?

Problem 7.

Which of the following sorting algorithms are stable: insertion sort, merge sort, heapsort, and quicksort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?

Problem 8.

Explain why the worst-case running time for bucket sort is Θ(n2). What simple change to the algorithm preserves its linear average-case running time and makes its worst-case running time O(n lg n)?

660_Graph.jpg

A1. Use the figure above as a model, illustrate the operation of heap sort on the array A = [5, 10, 7, 25, 8, 4]. Show all intermediate steps how the heap is transformed.

Reference no: EM131077386

Questions Cloud

Describe two inhibitors that might keep a person from moving : An outburst of aggression often starts with a triggering event. Prior to the event, the individual is at baseline. Crisis may have been brewing for sometime, and a certain event or series of events can cause the threshold of a person's self control ..
Prepare a departmental income statement : Prepare a departmental income statement for 2015. Prepare a departmental contribution to overhead report for 2015. Based on these two performance reports. should Jansen eliminate the ski department?
Calculate the fourier sine series : Math 121A: Homework 6. Consider the function f(x) = x(π - x) defined on 0 ≤ x ≤ π. Calculate the Fourier sine series fs and Fourier cosine series fc of f
Density of an object with a mass : What is the density of an object with a mass of 35 grams and a volume of 7 cm cubed?
What is the running time of quicksort : What is the running time of QUICKSORT when all elements of array A have the same value - Why do we analyze the expected running time of a randomized algorithm and not its worst-case running time?
Amount charged as a function : A car rental place charges a flat rate of $60 to rent a car plus 10 cents a mile. Write the amount charged as a function of how many miles the car is driven.
Two metallic terminals protrude from a device : 10. Under insolation conditions of 500 W/m2 (direct sunlight), and 10% solar cell efficiency (defined as the ratio of electrical output power to incident solar power), calculate the area required for a photovoltaic (solar cell) array capable of ru..
Find the vertex of the parabola : 1) Find the vertex of the parabola f(x) = x2 - 8x + 51 2) Solve the equation: x2 + x - 20 = 0
Pair of parallel lines : (a) Is the system inconsistent, or are the equations dependent, or neither? (b) Is the graph a pair of intersecting lines, a pair of parallel lines, or one line? (c) Does the system have one solution, no solution, or an infinite number of solutions

Reviews

Write a Review

Data Structure & Algorithms Questions & Answers

  Implement an open hash table

In this programming assignment you will implement an open hash table and compare the performance of four hash functions using various prime table sizes.

  Use a search tree to find the solution

Explain how will use a search tree to find the solution.

  How to access virtualised applications through unicore

How to access virtualised applications through UNICORE

  Recursive tree algorithms

Write a recursive function to determine if a binary tree is a binary search tree.

  Determine the mean salary as well as the number of salaries

Determine the mean salary as well as the number of salaries.

  Currency conversion development

Currency Conversion Development

  Cloud computing assignment

WSDL service that receives a request for a stock market quote and returns the quote

  Design a gui and implement tic tac toe game in java

Design a GUI and implement Tic Tac Toe game in java

  Recursive implementation of euclids algorithm

Write a recursive implementation of Euclid's algorithm for finding the greatest common divisor (GCD) of two integers

  Data structures for a single algorithm

Data structures for a single algorithm

  Write the selection sort algorithm

Write the selection sort algorithm

  Design of sample and hold amplifiers for 100 msps by using n

The report is divided into four main parts. The introduction about sample, hold amplifier and design, bootstrap switch design followed by simulation results.

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