CODEWITHSUNDEEP
calgorithmsortingtime-complexityquicksort
reish
reish

Reputation: 851

Trying to cause a "worse case" quicksort

I implemented a quicksort implementation in C and I'm trying to figure out what input is needed to cause a worse case performance.

According to wikipedia:

always choosing the last element in the partition as the pivot in this way results in poor performance (n^2) on already sorted lists, or lists of identical elements.

So I tried to do that, which resulted in the following code. The pivot is always the last element and the input is an already sorted list.

In order to prove that the complexity is indeed n^2, I created a global variable which I increment in each iteration, then finally print it.

I'd expected that the program would print:

Done in 64 iterations

However, it did it in 28 iterations. Maybe my understanding of the term "complexity" is wrong?

Upvotes: 0

Views: 140

Answers (2)

Deepu
Deepu

Reputation: 7610

The number of iterations is 28 for n=8.

The number of iterations is equal to n*(n-1)/2 = 8*7/2 = 28.

Now the function is f(n)=n*(n-1)/2 = n2/2 - n/2.

There for f(n) = O(n2/2 - n/2) = O((1/2)n2) = O(n2).

Thus for your input is in fact the worst case for Quicksort.

Upvotes: 1

nneonneo
nneonneo

Reputation: 179422

In every iteration, the list shrinks by one element because the pivot is moved and no longer counted. So, the total amount of iterations is 7+6+5+4+3+2+1 = 28.

Note that this is still quadratic, because it is equal to n*(n-1)/2.

Upvotes: 5

Related Questions