a)Describe how a variation of Quicksort can be used to solve the Selection Probl

Question

a)Describe how a variation of Quicksort can be used to solve the Selection Problem. (Hint consider which of the two parts to the partition contains the element you want.) What are the average and worst case time complexities?

b)Imagine a variation of Merge Sort in which at each call the array is divided into three lists, instead of two, that are individually sorted and then merged into one big sorted array. Explain why this variant’s worst case time complexity is described by the recurrence T(1) = 0, T(n) = 3T(n/3) + 2n – 3.  

Explanation / Answer

QuickSort worst case time complexity

In quicksort, one of the main concern is choosing the pivot element. In quicksort, worst case occur when we select pivot element as the smallest element of the list or we select pivot element as the greatest element of the list. This happen if suppoes we have already sorted array and we are choosing first or the last element as pivot element for our sorting. And in this worst case worst case time complexity is O(n2). Becuase in this case one side of the pivot
element will be empty and we recursively do quicksort on n-1 elements

QuickSort average case time complexity

The average case quicksort time complexity is O(nlogn). Its occur when we chose pivot element as the middle of list and both the parts of pivot element having same number of elements.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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