CODEWITHSUNDEEP
sortingbig-o
jcm
jcm

Reputation: 5659

Running time of quicksort when attempting to sort an array of duplicate values

I am considering the case where quicksort is run on an array of all the same values, e.g:

[1,1,1,1,1,1,1,1,1,1,1,1.......1]

Is it correct that the running time in this scenario would be O(n^2)?

Upvotes: 0

Views: 895

Answers (2)

Jerry Coffin
Jerry Coffin

Reputation: 490198

There is no one correct answer for all implementations of QuickSort.

Specifically, it depends on how you choose your pivot.

If you choose the first element as the pivot, yes, this would give O(N2).

If you choose the middle element or a typical median of 3 as the pivot, it'll be O(N log N).

Upvotes: 1

Kevin Dreßler
Kevin Dreßler

Reputation: 447

Correct. For already ordered arrays and reverse ordered arrays the median of three rule avoids the quadratic runtime. See https://en.wikipedia.org/wiki/Quicksort#Repeated_element for improving the runtime on arrays where all entries are the same.

Upvotes: 1

Related Questions