CODEWITHSUNDEEP
arraysalgorithmsortingarray-algorithms
alcol92
alcol92

Reputation: 165

Consider a version of quicksort where the pivot is always chosen to be the first element of the relevant subarray

My question is: consider a version of quicksort where the pivot is always chosen to be the first element of the relevant subarray, and the algorithm sorts its input array from least to greatest. Is it true that no input array causes the algorithm to make a greater number of comparisons than the number of comparisons it makes on an already sorted array?

Upvotes: 0

Views: 98

Answers (1)

Ishamael
Ishamael

Reputation: 12795

The worst case scenario for QuickSort is when on every iteration it splits the array of size n into two with sizes 0 and n-1. Since this is precisely what happens in your case (the pivot will always be the smallest element in the remaining array), then I believe it is correct that no input array will result in more comparisons than an array that is already sorted.

Upvotes: 1

Related Questions