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 best case of QuickSort comparable in the number of comparisons required?
(Select one or more of the following answers)

MergeSort

None of these

BubbleSort

SelectionSort

Reference Questions:

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

None of these

BubbleSort

SelectionSort

Explanation / Answer

29) In the best case quick sort is comparable to merge sort.

30) T(n) = 2*T(n/2)+O(n)

31) T(n) = T(n-1) + O(n)

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

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