Which of the following statements are true regarding Quicksort?

Question

BlackTom AI · Accepted Answer

Median-of-medians produces a pivot that guarantees a constant fractional split and can be found in Θ(n) worst-case time, so using it to choose the pivot fixes Quicksort’s balance.

1) Relevant concepts
- Median-of-medians: a selection algorithm that finds the true median (or an element within fixed rank bounds) in Θ(n) worst-case time and guarantees that the pivot lies between fixed percentiles (e.g., between the 30th and 70th percentile).
- Quicksort recurrence: T(n) = T(size_left) + T(size_right) + Θ(n) for partitioning and pivot selection.
- Dutch National Flag (3-way partitioning) handles many equal keys; without it, many equal elements can produce very unbalanced partitions.

2) Step-by-step reasoning
- If the pivot is the true median (or similarly well-balanced by median-of-medians) and there are no duplicate elements, the array splits roughly in half: size_left ≈ n/2 and size_right ≈ n/2.
- Pivot selection using median-of-medians costs Θ(n) per level (selection + partition).
- Recurrence becomes T(n) = 2 T(n/2) + Θ(n).

3) Calculations / intermediate steps
- Apply Master Theorem: a = 2, b = 2 → n^{log_b a} = n. With f(n) = Θ(n), this is case 2 → T(n) = Θ(n log n).

4) Why the correct answers are correct
- Because median-of-medians guarantees balanced splits and costs Θ(n) per partitioning level, both the worst-case and best-case complexities of Quicksort (without Dutch National Flag and assuming no repeated elements) resolve to Θ(n log n). The worst-case is no longer Θ(n^2) because the pivot selection prevents highly skewed splits; the best-case is Θ(n log n) because even in the ideal balanced split the selection cost per level remains Θ(n).

5) Why other options are incorrect
- Option a (Θ(n) best case): false because selection + partitioning at each of Θ(log n) levels yields Θ(n log n), not Θ(n).
- Option c (Θ(n^2) worst case): false because median-of-medians prevents the pathological skewed splits that cause Θ(n^2).

6) Conclusion / confirmation
Therefore statements b and d are correct. This matches the provided answer: b and d.

Which of the following statements are true regarding Quicksort?多项选择题

类似问题

When QuickSort repeatedly produces highly skewed partitions (for example, the pivot always becomes the smallest or largest element), what is the resulting time complexity, given the explanations below?

Sorting Complexity For an array of N integers that are in the ascending order as shown below, give the time complexity for each sorting algorithm. 1,2,3, ... , N-2, N-1, N 1: Insertion Sort 2: Selection Sort 3: Bubble Sort 4: Merge Sort 5: Tree (BST) Sort (hint:Is BST very unbalanced?)

Which of the following statements are true?

Which of the following is not a property of bubble sort?

Identify the code that sorts the numbers in descending order. def selection_sort(numbers): for i in range(len(numbers) - 1): index = i XXX temp = numbers[i] numbers[i] = numbers[index] numbers[index] = temp

In bubble sort, how many passes are needed to guarantee the list is sorted?

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单