0
$\begingroup$

I have read that when pivot element is choosen as Median, then QS Algorithm gets nearly balanced splits and have time complexity of O(nlogn), but my doubt is what if all the elements of the input are same like (2,2,2,2,....,2) and pivot is still the median element, then what type of partitions QS will get as left and right subarray and what will be the time complexity. O(nlogn) or O(n^2)

This is not a homework question, I'm not in school/college anymore.

$\endgroup$
1
$\begingroup$

It depends on the partition algorithm used. Some might be $O(n^2)$ if they put all equal elements on the same side while others remain $O(n \log n)$ if they split the equal elements.

$\endgroup$
  • $\begingroup$ May you elaborate more? Also, I'm saying Median is picked as pivot by the Partition algorithm used. $\endgroup$ – Geeklovenerds May 22 at 13:03
  • $\begingroup$ Are you referring to Hoare and Lumoto Partition? $\endgroup$ – Geeklovenerds May 22 at 13:03
  • $\begingroup$ @Geeklovenerds Hoare, Lumoto and others. There are a ton of different partitioning algorithms all described as "Quicksort". Some also prescribe a particular pivot selection, others just assume you give it a pivot element. $\endgroup$ – orlp May 22 at 13:06
0
$\begingroup$

Writing a Quicksort implementation where n equal items take $O(n^2)$ is just stupid.

A good implementation will split the array into items less than the median, equal to the median, and greater than the median. That will sort an array of all equal elements in O(n).

$\endgroup$
  • $\begingroup$ Sorry, I'm just reading up on Quicksort and I didn't get you. $\endgroup$ – Geeklovenerds May 22 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.