For comparison based algorithms for sorting an array A[1...n]: quicksort(using t

Question

For comparison based algorithms for sorting an array A[1...n]: quicksort(using two-finger partition algorithm) and heapsort. For each algorithm, answer the following questions:

a. What is the worst-case running time of the algorithm? Describe the structure of an input array on which the algorithm exhibits its worst-case running time.

b. What is the best-case running time of the algorithm? Describe the structure of an input array on which the algorithm exhibits its best-case running time.

c. What is the average-case running time of the algorithm? Explain.

Explanation / Answer

Worst case for quicksort=O(n2)

It occurs when the pivot choosed happens to be the maximum or minimum element of the array.After partitioning the array gets devided into two parts and the time complexity becomes T(n)=T(k)+T(n-k) but in worst case it gets devided into sizes of 1 and n-1 so T(n) becomes T(1)+T(n-1).This recursion's solution is T(n)=cn2.If we have an already sorted array as input it gives such array can give such a worst case time complexity.

WORST CASE-int arr[]={1,2,3,4,5}

For heapsort both the worst and the best cases are O(nlogn).No matter what the input is since the algorithm has to build a max-heap or min-heap it will anyway take O(nlogn) time to do so so asymptotically we cant have different complexities but ther may be a difference of a contant between various inputs.

Best case of quicksort-It occurs when the partition devides the array into two equal halves.O(nlogn)

Example={2,4,1,5,3}

pivot =3

after partition={2,1,3,5,4}

T(n)=2T(n/2)+c

Best case of heapsort=O(nlogn)

Average running time for quicksort is O(nlogn) because time for quicksort includes time to do partitioning + time to sort the two partitions,partition is O(n) and suppose the two partitions are of lengths k and n-k ,then T(n)=T(k)+T(n-k)+cn.This recursion give T(n)=cnlogn for all k except k=1 or k=n-1

Average case for heapsort is O(nlogn)

Heapsort(A)

Build-max-heap(A)

for i=A.length downto2

exchange A[1] with A[i]

A.heapsize--

Maxheapify(A,1)

Now, builtmaxheap take O(nlogn) time.each for loop runs for O(logn) time since heapify takes O(logn) time and for looop runs for O(n) time hence T(n)=O(nlogn)+O(nlogn)=O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.