Refer back to exercises 29 and 31 from chapter 3 section 3 for the following pro

Question

Refer back to exercises 29 and 31 from chapter 3 section 3 for the following problem:
Exercise 29 describes the best case of QuickSort and Exercise 31 describes the worst case of QuickSort with respect to comparisons between list elements.

To which sorting algorithm (SelectionSort, BubbleSort, MergeSort) is the worst case of QuickSort comparable in the number of comparisons required?
(Select one or more of the following answers)

MergeSort

BubbleSort

None of these

SelectionSort

29. Suppose that for each pass, each pivot element splits its sublist into two equal-length lists, each approximately

half the size of the sublist (which is actually very difficult to achieve). Write a recurrence relation

for the number of comparisons between list elements in this case.

31. Suppose that for each pass, each pivot element splits its sublist (which has k elements) into one empty list

and one list of size k 1. Write a recurrence relation for the number of comparisons between list elements

in this case.

MergeSort

BubbleSort

None of these

SelectionSort

Explanation / Answer

In worst case, quick sort takes O(n^2). No. of comparisons in bubble sort decreases with the increase in no. of iterations while in selection sort it will remain constant irrespective of the data. So, in comparison to no. of comparisons required selection sort is comparable to quick sort.

29.) Since each pass divides the sublist into 2 equal halves. Therefore, recurrence relation will be t(n) = 2t(n) + n

30.) Since each pass splits into one empty list and one list of size k-1. Therefore, recurrence relation will be t(n) = t(n-1) + n

Hope it helps, do give your response.

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

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