0

Can we always avoid the worst case of Quick sort using median-of-3 method?

허지용
  • 1
  • 1
  • 1

1 Answers1

0

The Quick Sort algorithm works as follows:

  1. If the number of elements in S is 0 or 1, then return (base case).
  2. Pick any element v in S (called the pivot).
  3. Partition the elements in S except v into two disjoint groups
  4. Return {QuickSort(S1 ) + v + QuickSort(S2 )}

The worst case for Quick Sort using the median-of-3 method is when the selected pivot reduces the problem size by the smallest possible amount. This means that the selected pivot provides as far-off a partition as is possible. And since we are using the median-of-3 method, the selected partition cannot be either the largest or smallest element since our selected method ensures that the partition has an element larger and smaller than the median.

Therefore, if you mean can we avoid the worst case of a true O(n^2) scenario where every element is in order backward value-wise and we must partition through the entire list, then yes we can avoid the worst case scenario.

The point of using the median-of-3 method is to bring us closer to the average run-time of quick sort: O(nlogn). This is because by avoiding the farthest elements in the list to choose our partition, we can minimize our deviation from the best/average case run-time of O(nlogn).

Using the median-of-3 method will allow us to never have to search the entire list for the right partition but rather start somewhere in the middle. Therefore, we can avoid the worst-case run-time of O(n^2) and settle at the average run-time of O(nlogn)

Jake Aronskind
  • 11
  • No mean effort, but not an answer to walk away with insights/knowledge from, I'm afraid. 3. lacks a characterisation of said `two disjoint groups`: Items belonging *not after* the pivot and *not before*, respectively. (Regarding 4., I've encountered curly braces as a set notation more often than not.) With "*worst result of a partition of* n *elements has a cardinality of* n-k", **the asymptotic worst case is the same for *any* fixed k>0** (2 with MoT). The paragraph on *expected average behaviour* looks bang-on right - in sharp contrast to `we can [exclude] the worst-case run-time of O(n^2)`. – greybeard Dec 04 '18 at 08:22