Quick sort

Question

13, 60,19,52,45,27,41,30,34,32.. Is this sequence in an array a worst case for Quicksort if first element is choosen as pivot always?

I have tried to run algorithm of Quicksort on this sequence but not getting it.. Can anyone please explain this?

 

My approach is::

After 1st iteration array is splitted into(pivot is 13):

sub-array1:: null

subarray 2:: 60,19,52,45,27,41,30,34,32

 

applying quicksort on subarray 2:

After 2nd iteration sub-array 2 is splitted into(pivot is 60):

sub-array 21:: 32,19,52,45,27,41,30,34

sub-array 22:: 60

 

applying quicksort on subarray 22(pivot is 32):

After 3rd iteration sub-array 22 is splitted into:

sub-array 221:: 30,19,27

sub-array 223:: 52,41,45,34

 

and seeing this iteration 3 we can say this is not a worst case hence for whole array it would not be a worst of if sorting using Quicksort..

 

Can someone please tell me where I am thinking wrong??

Comments

In quicksort Worst case comes when array is already sorted or almost sorted because then most of the time pivot element divides the array such that all elements other than pivot go to one side only and hence approximately n level tree comes and in each level partition algorithm runs which takes total time complexity approximately equal to O($n^{2}$).

Answer 1

No, Nothing can be said.

beause worst cases, best cases can be observed only for n length arrays. You can notice if we will try to see number of time pivot choosen here, if you will see carefully it can be said as n/Constant as well as it can also be said as only some constant times pivot has been selected. So saying anything would be wrong without observing pattern for n length Arrays.

“If Partition algorithm is doing only 1 partition of array for Asymptotically n times then it’ll be considered as worst case scenerio.”

also by default the pivot choosen is left most in the default QuickSort Algorithm.

 

 

 

 

 

 

Comments

Yes i agree I have understood this is not a worst case scenario as we can see in iteration 3..

Thank you.