retagged by
1,590 views

2 Answers

Best answer
1 votes
1 votes

The worst case occurs when the partition function always picks greatest or smallest element as pivot. If we consider last element is always picked as pivot, the worst case would occur when the array is already sorted in increasing or decreasing order.

The normal time complexity of quicksort is

T(n) = T(k) + T(n-k-1) + theta(n)

The first two terms are for two recursive calls, the last term is for the partition process. k is the number of elements which are smaller than pivot.

In worst case scenario k=0

T(n) = T(0) + T(n-1) + theta(n) = T(n-1) + theta(n)

The number of swaps in the worst case scenario is the time complexity of the partition function and the number of times the partition function is called.

So, partition function is called n times in the worst case scenario and we all know the time complexity of the partition function is O(n)  making maximum number of swaps O(n2).

selected by
0 votes
0 votes

The maximum number of swaps will occur when you will choose the pivot as the smallest or the largest everytime (unintentionally).

Let say we get the largest number everytime.

So, the first pivot will require n swaps

second will require n-1 swaps

third will require n-2 and so on.

the number of swaps will become n+ (n-1)+(n-2)--------- 1

or

1+ 2 + 3 +--------n

which is n(n+1)/2

which is O(n2)

Related questions

1 votes
1 votes
2 answers
2
Shubhanshu asked Dec 1, 2018
5,040 views
Is Quick sort an adaptive sorting Algorithm? I think no. Because as per the definition given in the Wikipedia is that A adaptive sorting Algorithm is one who takes the ad...