CODEWITHSUNDEEP
algorithmquicksort
Shubham Goyal
Shubham Goyal

Reputation: 667

Number of comparisons in quick sort variation

Will the number of comparisons differ when we take the last element as the pivot element in Quick sort and when we take the first element as the pivot element in the quick sort??

Upvotes: 0

Views: 1059

Answers (2)

Imesha Sudasingha
Imesha Sudasingha

Reputation: 3570

No it will not. In quick sort, what happens is, we chose a pivot element(say x). Then divide the list to 2 parts larger than x and less than x.

Therefore, the number of comparisons change slightly proportional to the recursion depth. That is, the more deeper the recursive function goes, more the number of comparisons to be made to divide the list to 2 parts.

The recursion depth differs - More the value of x can divide the list to similar length parts, lesser will be the recursion depth.

Therefore, the conclusion is, it doesn't matter whether you chose the first or the last element as the pivot, but whether that value can divide the list to 2 similar length lists.

Edit The more the pivot is close to the median, lesser will be the complexity (O(nlogn)). The more the pivot is close to the max or min of the list, complexity increases (up to O(n^2))

Upvotes: 1

Rudrani Angira
Rudrani Angira

Reputation: 986

When a first element or last element is chosen as pivot the number of comparisons remain same but it is the worst case as the array is either sorted or reverse sorted. In every step ,numbers are divided as per the following recurrence.

T(n) = T(n-1) + O(n) and if you solve this relation it will give you the complexity of theta(n^2)

And when you choose median element as pivot it gives a recurrence relationship of 

T(n) = 2T(n/2) + \theta(n) which is the best case as it gives complexity of `nlogn`

Upvotes: 0

Related Questions