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$

2 Answers 2

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$
3
  • $\begingroup$ May you elaborate more? Also, I'm saying Median is picked as pivot by the Partition algorithm used. $\endgroup$ Commented May 22, 2019 at 13:03
  • $\begingroup$ Are you referring to Hoare and Lumoto Partition? $\endgroup$ Commented May 22, 2019 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
    Commented May 22, 2019 at 13:06
-1
$\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$
1
  • $\begingroup$ Sorry, I'm just reading up on Quicksort and I didn't get you. $\endgroup$ Commented May 22, 2019 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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