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.
2 Answers 2
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.
-
$\begingroup$ May you elaborate more? Also, I'm saying Median is picked as pivot by the Partition algorithm used. $\endgroup$Geeklovenerds– Geeklovenerds2019年05月22日 13:03:12 +00:00Commented May 22, 2019 at 13:03
-
$\begingroup$ Are you referring to Hoare and Lumoto Partition? $\endgroup$Geeklovenerds– Geeklovenerds2019年05月22日 13:03:54 +00:00Commented 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– orlp2019年05月22日 13:06:17 +00:00Commented May 22, 2019 at 13:06
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).
-
$\begingroup$ Sorry, I'm just reading up on Quicksort and I didn't get you. $\endgroup$Geeklovenerds– Geeklovenerds2019年05月22日 15:07:19 +00:00Commented May 22, 2019 at 15:07