✏️ Explanatory Question
In its worst case, QuickSort behaves like:
(a) Bubble Sort
(b) Selection Sort
(c) Insertion Sort
In its worst case, QuickSort behaves like:
(a) Bubble Sort
(b) Selection Sort
(c) Insertion Sort
Ans. (a) Bubble Sort. In the worst case, the pivot may repeatedly be the largest element, producing one-sided partitions and quadratic running time. This resembles Bubble Sort, where each pass places the largest remaining element at the end.
💡 Explanation:
QuickSort reaches its worst case when every selected pivot is the smallest or largest element in the current subarray. Each partition then places only one element in its final position and leaves a subproblem containing n − 1 elements.
If the largest element is repeatedly selected as the pivot, each partition places that element at the far end and then recursively processes the remaining elements. This is similar to Bubble Sort, where each pass moves the largest unsorted element to its correct position at the end.
The amount of work is:
(n − 1) + (n − 2) + … + 2 + 1 = n(n − 1)/2 = O(n2)
Therefore, both worst-case QuickSort and Bubble Sort have quadratic time complexity: O(n2).
Memory tip: In this analogy, each pass places one extreme element at the end, and the remaining problem becomes smaller by only one element.