Optimized version of quicksort

Assignment Help Basic Computer Science

Reference no: EM13968264

1. Implement an optimized version of quicksort and experiment with combinations of the following:

a. pivot: ?rst element, middle element, random element, median of three, median of ?ve

b. cutoff values from 0 to 20

2. Write a routine that reads in two alphabetized ?les and merges them together, forming a third, alphabetized, ?le.

3. Suppose we implement the median-of-three routine as follows: Find the median of a[left], a[center], a[right], and swap it with a[right]. Proceed with the normal partitioning step starting i at left and j at right-1 (instead of left+1 and right-2).

a. Suppose the input is 2, 3, 4, ... , N - 1, N, 1. For this input, what is the running time of this version of quicksort?

b. Suppose the input is in reverse order. For this input, what is the running time of this version of quicksort?

Reference no: EM13968264

Questions Cloud

Comparison-based sorting algorithm : 1. Prove that any comparison-based sorting algorithm requires 0.(N log N) compar- isons on average.

Focusing on improving health care delivery : It is increasingly clear that focusing on improving health care delivery is not suf?cient to reduce health disparities. How can we as a society begin to affect the broader factors that underlie racial and ethnic disparities in health?

Cost is irrelevant to the aggregate production plan : Which one of the following cost is irrelevant to the aggregate production plan?

Convey to her superiors using all of the proper channels : Lisha is an engineer at a robotics lab who has discovered that the CEO of her company has been embezzling money from the company for years. She had sufficient evidence of the crime, which she tried to convey to her superiors using all of the proper c..

Optimized version of quicksort : 1. Implement an optimized version of quicksort and experiment with combinations of the following: a. pivot: ?rst element, middle element, random element, median of three, median of ?ve

How are fictional scientists viewed in the media : Influences of the Media- How are fictional scientists viewed in the media? Give 2 examples of either heroes or villains and How is science viewed in the fictional media

Estimating the comparison-based algorithm : a. Prove that any comparison-based algorithm to sort 4 elements requires 5 comparisons. b. Give an algorithm to sort 4 elements in 5 comparisons.

What would you advise her in evaluating the service package : Joan is the operations manager at Dark Light Communications, a services company. She has been told that the Operations function needs to pay more attention to the "service package" in order to be able to support the competitive priorities of the busi..

Ethical behavior and social responsibility to their behavior : Discuss specific activities where Operations Managers can apply ethical behavior and social responsibility to their behavior. Use examples from the course materials to expand your analysis.

User Account

All Pages